Simple Sorting Techniques DIK-013 Data Structure Diploma 3 Years in Informatics Management
Irvanizam Zamanhuri, M.Sc Computer Science Study Program Syiah Kuala University http://www.informatika.unsyiah.ac.id/irvanizam Email:
[email protected]
Sorting Technique o
o
In general, we can classify the sorting technique into two categories. - Elementary sorting methods - Advanced sorting methods. Elementary sorting methods are:
- bubble sort q
- selection sort - insertion sort Advanced sorting methods are: - shell sort - quick sort - merge sort - Radix sort
Bubble Sort o
o
o
o
Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.
Bubble Sort Algorithm (1/2) q Perbandingan data dilakukan dari posisi pertama atau posisi terakhir bergeser satu persatu sampai semua data dibandingkan. q Jika terdapat N data dan data terkoleksi dari urutan 0 sampai dengan N-1 maka algoritma pengurutan dengan metode bubble sort adalah sebagai berikut:
Bubble Sort Algorithm (2/2) 1. Bandingkan posisi data i = 0 dan j = 1. 2. Jika data diposisi i lebih besar daripada data diposisi j, maka data diposisi i ditukar dengan data diposisi j (swap). Jika tidak penukaran posisi tidak dilakukan. 3. Kemudian, lakukan perbandingan data diposisi i = 1 dan data diposisi j = 2. Lakukan langkah 2, begitu juga untuk data berikutnya hingga i = N-2 dan j = N-1. 4. Ulangi langkah 1, 2 dan 3 untuk data diposisi 0 sampai dengan data diposisi N-2, karena data di posisi N-1 adalah data dengan nilai terbesar. Untuk tahap selanjutnya data yang dibandingkan akan semakin berkurang sebab data dengan nilai yang lebih besar akan terposisi dibagian sebelah kanan data.
Example q Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort algorithm. q In each step, elements written in bold are being compared. q First Pass: ( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps them. ( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), Swap since 5 > 4 ( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), Swap since 5 > 2 ( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Continue q Second Pass: (14258) → (14258) ( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), Swap since 4 > 2 (12458) → (12458) (12458) → (12458) Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted. q Third Pass: (12458) → (12458) (12458) → (12458) (12458) → (12458) (12458) → (12458) Finally, the array is sorted, and the algorithm can terminate.
Implementation in C void bubblesort(int arr[]) { int i,j; for (i = N; --i>=0;) { for (j = 0; j
arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }
Performance q Bubble sort has worst-case and average complexity both О(n2), where n is the number of items being sorted. q its O(n2) complexity means it is far too inefficient for use on lists having more than a few elements.
Selection Sort q Selection sort merupakan perbaikan dari metode bubble sort dengan mengurangi jumlah perbandingan. q Selection sort merupakan metode pengurutan dengan mencari nilai data terkecil dimulai dari data diposisi 0 hingga diposisi N-1. q Jika terdapat N data dan data terkoleksi dari urutan 0 sampai dengan N-1 maka algoritma pengurutan dengan metode selection sort adalah sebagai berikut:
Algoritma • Cari data terkecil dalam interval j = 0 sampai dengan j = N-1 • Jika pada posisi pos ditemukan data yang terkecil, tukarkan data diposisi pos dengan data di posisi i jika k. • Ulangi langkah 1 dan 2 dengan j = j+i sampai dengan j = N-1, dan seterusnya sampai j = N - 1.
Example
Animasi
Implementation in C void selectionsort(int arr[]) { int i,j; for (i = 0; i < N; i++) { int min = arr[i]; int pos = i; for (j = i; j < N; j++) { if (arr[j] < min) { /* Cari nilai yang terkecil */ min = arr[j]; pos = j; } } if(i!=pos) { /* Tukar nilai terkecil ke arr[i] jika pos tdk sama i */ int temp = arr[i]; arr[i] = arr[pos]; arr[pos] = temp; } } }
Performance q It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. q Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.
Insertion Sort • Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. • Metode pengurutan selection sort sering dipakai oleh orang saat bermain kartu bridge dalam mengurutkan kartunya, yaitu dengan cara menyisip kartu yang lebih kecil ke urutan sebelum posisi kartu yang dibandingkannya.
Example
Animasi
Implementation in C void bubblesort(int arr[]) { int i,j; for (i = N; --i>=0;) { for (j = 0; j arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }
Performance (1/2) q The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., O(n)). q During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array. q The worst case input is an array sorted in reverse order. In this case every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. q For this case insertion sort has a quadratic running time (i.e., O(n2)).
Performance (2/2) q The average case is also quadratic (O(n2)), which makes insertion sort impractical for sorting large arrays. q However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quick sort.
Advantages (1/2) • Simple implementation • Efficient for (quite) small data sets • Adaptive, i.e. efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions • More efficient in practice than most other simple quadratic, i.e. O(n2) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
Advanteges (2/2) • Stable, i.e. does not change the relative order of elements with equal keys • In-place, i.e. only requires a constant amount O(1) of additional memory space • Online, i.e. can sort a list as it receives it
Reference o o o o o
http://www.informatika.unsyiah.ac.id/tfa/ds/bubblesort.pdf http://www.informatika.unsyiah.ac.id/tfa/ds/selectionsort.pdf http://en.wikipedia.org/wiki/Insertion_sort http://en.wikipedia.org/wiki/Bubble_sort http://en.wikipedia.org/wiki/Selection_sort
