Pengurutan Data (Sorting)

1. Insertion Sort

Prinsip kerja dari pengurutan data akan dilakukan berulang-ulang menyisipakan (insert) setiap elemen data ke posisinya yang benar sehingga dihasilkan urutan data yang optimal.

Kode programnya:

mark first element as sorted
for each unsorted element
  'extract' the element
  for i = lastSortedIndex to 0
    if currentSortedElement > extractedElement
      move sorted element to the right by 1
    else: insert extracted elemen

untuk lebih jelasnya tentang Insertion Sort bisa lihat video berikut ini:

2. Selection Sort

Prinsip kerjanya dengan cara memilih elemen data terkecil yang selanjutnya dibandingkan dan ditukarkan dengan elemen pada data awal yang dilakukan secara berulang-ulang sehingga dihasilkan urutan data yang optimal.

Kode programnya:

repeat (numOfElements - 1) times

  set the first unsorted element as the minimum

  for each of the unsorted elements

    if element < currentMinimum

      set element as new minimum

  swap minimum with first unsorted position

untuk lebih jelasnya tentang Selection Sort bisa lihat video berikut ini:

3. Pengurutan Gelembung udara (Bubble Sort)
Pengurutan menggunakan prinsip gelembung udara (bubble) yang akan berdgerak satu per satu sampai dihasilkan urutan data yang optimal.

Kode program nya:

do

  swapped = false

  for i = 1 to indexOfLastUnsortedElement

    if leftElement > rightElement

      swap(leftElement, rightElement)

      swapped = true; swapCounter++

while swapped

untuk lebih jelasnya tentang Bubble Sort bisa lihat video berikut ini:

4. Merge Sort
Prinsip kerjanya dengan cara membagi menjadi dua bagian dan dilakukan pengurutan disetiap bagian dan dilakukan berulang-ulang sampai dengan kondisi urutan yang optimal

Kode programnya:

split each element into partitions of size 1

recursively merge adjancent partitions

  for i = leftPartStartIndex to rightPartLastIndex inclusive

    if leftPartHeadValue <= rightPartHeadValue

      copy leftPartHeadValue

    else: copy rightPartHeadValue; Increase InvIdx

copy elements back to original array

untuk lebih jelasnya tentang Merge Sort bisa lihat video berikut ini:

5. Quick Sort

Pengurutan data dengan membandingkan dengan metode divide and conqueror, mengurutkan dengan sangat cepat (quick), sangat komplex dan diproses secara rekursif.

Kode programnya:

for each (unsorted) partition

  set first element as pivot

  storeIndex = pivotIndex + 1

  for i = pivotIndex + 1 to rightmostIndex

    if element[i] < element[pivot]

      swap(i, storeIndex); storeIndex++

  swap(pivot, storeIndex - 1)

untuk lebih jelasnya tentang Quick Sort bisa lihat video berikut ini:

6. Randomized Quick Sort

merupakan perpanjangan dari Quick Sort di mana elemen poros dipilih secara acak

Kode programnya:

for each (unsorted) partition

  randomly select pivot, swap with first element

  storeIndex = pivotIndex + 1

  for i = pivotIndex + 1 to rightmostIndex

    if element[i] < element[pivot]

      swap(i, storeIndex); storeIndex++

  swap(pivot, storeIndex - 1)

untuk lebih jelasnya tentang Randomized Quick Sort bisa lihat video berikut ini: