Bubble sort a singly linked list

對一個 singly linked list 做 bubble sort

Method 1 :

void LinkedList::BubbleSortVer1( ){ if( !head ) return; bool change = true; while( change ){ //round Node *prev = NULL; Node *current = head; change = false; while( current->next != NULL ){ if( current->value > current->next->value ){ current = swap(current, current->next); change = true; if( prev != NULL ) // swap is unrelated to head, update prev' s next link prev->next = current; else // swap is related to head, change head pointer head = current; } prev = current; current = current->next; } } } Node* LinkedList::swap( Node* p, Node* q){ Node *temp = q->next; q->next = p; p->next = temp; return q; }

Main idea:

1. 藉由兩兩swap把最大的丟到最後面
2. 利用一個change flag 來判斷sorting完成否 (可以省略計算目前是第幾round)
3. 獨立的Swap function: 另外提出來做Node的Swap, 回傳Swap後, 前面的node, 如此可以讓iteration繼續下去
4. 利用兩個pointer, 一個是當前指標current, 一個是current的前一個node的指標prev
5. 比較當前node與下一個node的值, 來決定要不要swap
6. 注意head的位置會跑掉, 必須在swap判斷時, 判斷prev的位置; 如果prev的位置是在NULL, 表示目前current是head, 必須更新head, 否則更新prev的next連結位置
7. 前進prev和current

Method 2:

void LinkedList::BubbleSortVer2( ){ if( !head ) return; bool change = true; Node *prevHead = new Node(0, head); while( change ){ change = false; Node *prev = prevHead; Node *current = prev->next; while( current->next != NULL ){ if( current->value > current->next->value ){ prev->next = current = swap(current, current->next); change = true; } prev = current; current = current->next; } } head = prevHead->next; delete prevHead; } Node* LinkedList::swap( Node* p, Node* q){ Node *temp = q->next; q->next = p; p->next = temp; return q; }

Main idea:

1. 與作法1大致相同, 只差在此方法另外開一個新的dummy node去只向head, 此時, 可以在每次swap後, 都更新前一個node的next, 不用擔心前一個是NULL
2. 與作法1相比, 差了一個if的判斷式, 判別前一個node是不是非空, 來決定要不要更新前一個node的next, 或者是更新head

C++ code:

#include <iostream> using namespace std; class Node{ public: Node() : value(0), next(NULL) {} Node( int theValue, Node *theNext ) : value(theValue), next(theNext){} int value; Node *next; }; class LinkedList{ public: LinkedList( ); ~LinkedList( ); void push_front( int value ); void push_back( int value ); void delete_front( ); void show_element( ); void BubbleSortVer1( ); void BubbleSortVer2( ); private: Node* head; Node* swap( Node*, Node* ); }; LinkedList::LinkedList( ) : head(NULL){ } LinkedList::~LinkedList( ){ if( head ) delete_front( ); } void LinkedList::push_front( int value ){ Node *newNode = new Node(value, head); head = newNode; } void LinkedList::push_back( int value ){ if( !head ) push_front( value ); else{ Node *current = head; while( current->next != NULL ) current = current->next; Node *newNode = new Node(value, NULL); current->next = newNode; } } void LinkedList::delete_front( ){ if( !head ) return; Node *deleteNode = head; head = head->next; delete deleteNode; } void LinkedList::show_element( ){ Node *current = head; while( current ){ cout << current->value << " "; current = current->next; } cout << endl; } void LinkedList::BubbleSortVer1( ){ if( !head ) return; bool change = true; while( change ){ //round Node *prev = NULL; Node *current = head; change = false; while( current->next != NULL ){ if( current->value > current->next->value ){ current = swap(current, current->next); change = true; if( prev != NULL ) // swap is unrelated to head, update prev' s next link prev->next = current; else // swap is related to head, change head pointer head = current; } prev = current; current = current->next; } show_element( ); } } void LinkedList::BubbleSortVer2( ){ if( !head ) return; bool change = true; Node *prevHead = new Node(0, head); while( change ){ change = false; Node *prev = prevHead; Node *current = prev->next; while( current->next != NULL ){ if( current->value > current->next->value ){ prev->next = current = swap(current, current->next); change = true; } prev = current; current = current->next; } } head = prevHead->next; delete prevHead; } Node* LinkedList::swap( Node* p, Node* q){ Node *temp = q->next; q->next = p; p->next = temp; return q; } int main( ){ LinkedList list; list.push_back( 4 ); list.push_back( 7 ); list.push_back( 5 ); list.push_back( 1 ); list.push_back( 3 ); list.push_back( 2 ); list.push_front( 6 ); list.push_front( 0 ); list.show_element( ); list.delete_front( ); list.show_element( ); cout << "sorting list1: \n"; list.BubbleSortVer2( ); cout << "After sort: "; list.show_element( ); LinkedList list2; list2.push_back( 1 ); list2.push_back( 2 ); list2.push_back( 3 ); list2.push_back( 4 ); list2.push_back( 5 ); list2.push_back( 7 ); list2.push_back( 6 ); cout << "\nsorting list2: \n"; list2.BubbleSortVer2( ); cout << "After sort: "; list2.show_element( ); return 0; }

結論：

• bubble sort將大的往後swap到底端
• swap node另外實做一個函數, 回傳swap後前面的node, 非常重要且省事!
• round數不需要計算node總個數, 利用change flag來觀察是否已經完成sorting
• Maintain 兩個指標, previous及current, 其中previous是要用來更新swap後的鏈結方式, current是用來判斷pari間的大小關係

Reference:

http://www.sal.ksu.edu/faculty/tim/CMST302/study_guide/topic7/bubble.html