This article describes an implementation of the Bubble Sort Algorithm.
To make the implementation challenging, we will swap nodes instead of swapping content.
Bubble Sort implementation.
int bubblesort( Node ** list ){ Node * listPointer; Node * list1PointerNext; Node * list1Pointer; Node * list1PointerPrevious; Node * swapPointer; int listSize = 0; int i = 0; if( !list ){ return -1; } if( !*list ){ return 0; } if( !(*list)->next ){ return 0; } for( listPointer = *list; listPointer; listPointer = listPointer->next ){ listSize++; } //iterate the list for( i = 0; i < listSize; i++ ){ //for each iteration, swap adjacent element for( list1PointerPrevious = 0, list1Pointer = *list, list1PointerNext = (*list)->next; list1PointerNext; ){ if( list1PointerNext->content < list1Pointer->content ){ if( list1PointerPrevious ){ list1PointerPrevious->next = list1PointerNext; } else{ *list = list1PointerNext; } list1Pointer->next = list1PointerNext->next; list1PointerNext->next = list1Pointer; } if( list1PointerPrevious ){ list1PointerPrevious = list1PointerPrevious->next; } else{ list1PointerPrevious = *list; } list1Pointer = list1PointerPrevious->next; list1PointerNext = list1Pointer->next; } } return 0; }
Cool interview question.
What is the Big-Oh time!?