Cisco Systems Interview Question
Software Engineer / DevelopersTeam: Switching Softwares
Country: United States
Interview Type: Phone Interview
Bubble Sort, with O(n^2) time complexity, I think without additional memory, this is best solution, and use isSorted and pEnd to reduce complexity too.
struct Node
{
Node *next;
int value;
};
Node* BubbleSortList(Node *pHead)
{
if ( pHead == NULL || pHead->next == NULL ) // Empty or only one node case.
return pHead;
bool isSorted = false;
Node *pEnd = NULL; // point to last loop sorted item.
Node *pLastSwapNode = NULL;
while (pEnd != pHead && isSorted == false)
{
isSorted = true;
Node *pCurrent = pHead;
while (pCurrent->next != pEnd)
{
if (pCurrent->value > pCurrent->next->value )
{
swap(pCurrent->value, pCurrent->next->value); // don't swap node, just swap its value.
isSorted = false;
pLastSwapNode = pCurrent->next; // record swap last node.
}
pCurrent = pCurrent->next;
}
pEnd = pLastSwapNode;
}
return pHead;
}
void sortList(Node* h)
{
Node *cur1,*prev1,*next1,*cur2,*prev2,*next2;
prev1=h;
cur1=h->next;
while(cur1!=NULL)
{
next1=cur1->next;
prev2=h;
cur2=h->next;
while(cur2!=cur1)
{
next2=cur2->next;
if(cur2->data>cur1->data)
{
prev2->next=cur1;
cur1->next=cur2;
prev1->next=next1;
cur1=next1;
break;
}
prev2=prev2->next;
cur2=cur2->next;
}
if(cur2==cur1)
{
prev1=prev1->next;
cur1=cur1->next;
}
}
}
/*Sorting of linklist using bubble sort */
void sort_list ( LIST *head) {
int count=0,tmp,i;
LIST *node;
node=head;
/*count the number of elements*/
while (node!=NULL){
count++;
node=node->next;
}
/*do a bubble sort */
for ( i=1;i<count;i++){
node = head;
while(node->next!=NULL){
if(node->value > node->next->value)
{
tmp = node->value;
node->value = node->next->value;
node->next->value = tmp;
}
node = node->next;
}
}
}
Selection sort:
public static void sortList(Node head) {
Node tail = head;
while (tail.next != null) {
tail = tail.next;
}
Node n = head;
Node prev = null;
Node max = null;
Node prevForMax = null;
while (tail != head) {
max = tail;
n = head;
prevForMax = null;
prev = null;
while (n != tail) {
if (n.d > max.d) {
max = n;
prevForMax = prev;
}
prev = n;
n = n.next;
}
if (max != tail) {
if (prevForMax != null) {
prevForMax.next = tail;
}
if (max == prev) {
max.next = tail.next;
tail.next = max;
} else {
Node temp = tail.next;
tail.next = max.next;
prev.next = max;
max.next = temp;
}
}
if (max == head) {
head = tail;
}
if (max != prev) {
tail = prev;
}
}
//Node.printList(head);
}
This won't work in all cases.
The while loop breaks out after a single pass in some cases.
What happens if (list.first.data < list.first.nextLink.data) after the first pass. It should not break out simply.
can use simple bubble sort.... Though it has complexity of n^2, it solves the problem at least.
try insertion sort. that is efficient than bubble + inplace + no traverse back too
- Anonymous July 01, 2012