Definisi Algoritma Pengurutan
Algoritma pengurutan / Sorting algoritma adalah algoritma yang bertujuan untuk mengatur urutan dari sekumpulan elemen dalam format tertentu dengan memilah elemen yang memenuhi syarat yang ditentukan.
Dalam dunia pemograman Algoritma pengurutan / Sorting algoritma adalah hal yang mendasar. Hal ini disebabkan karena Algoritma pengurutan / Sorting algoritma memiliki kompleksitas yang dapat menyesesaikan suatu persoalan secara efisien untuk mendukung performa komputasi. Algoritma pengurutan / Sorting algoritma juga dapat memudahkan dalam pencarian dan pengambilan data.
Dalam pemrosesan data, algoritma ini membuat pemrosesan data berikutnya menjadi lebih mudah dan efisien karena data tersebut sudah berada dalam urutan yang ditentukan. Urutan yang paling sering digunakan dalam algoritma pengurutan / Sorting algoritma adalah urutan berdasarkan numerik dan leksikografis.
Teknik Algoritma Pengurutan / Sorting Algoritma
Algoritma sorting dapat dilakukan dalam berbagai teknik, seperti:
In-place Sorting dan Not-in-place Sorting
Sebuah algoritma dapat dikategorikan sebagai In-place maupun Not-in-place berdasarkan bagaimana alokasi memori yang diperlukan untuk melakukan proses pengurutan.
In-place sorting melakukan proses pengurutan elemen tanpa memerlukan alokasi memori tambahan. Proses pengurutan dilakukan dalam kumpulan elemen itu sendiri. Algoritma pengurutan in-place memiliki keunggulan dalam pengunaan memori.
Not-in-place sorting melakukan proses pengurutan nilai input dengan memanfaatkan alokasi memori tambahan. walaupun Algoritma not-in-place sorting menggunakan lebih banyak memori, tapi Algoritma not-in-place sorting lebih unggul dalam waktu proses dibanding dengan Algoritma in-place sorting.
Stable dan Unstable Sorting
Algoritma pengurutan stable dalam proses pengurutan tidak mengubah posisi elemen yang memiliki nilai yang sama. Hasil output dari stable algoritma menampilkan elemen dengan nilai yang sama memiliki urutan yang serupa dengan urutan elemen input yang belum diproses.
Sedangkan algoritma pengurutan unstable mengubah urutan elemen yang memiliki nilai yang sama, sehingga hasil output dari not stable sorting menampilkan posisi elemen serupa yang berubah dari urutan input yang belum diproses
Adaptive dan Non-Adaptive Sorting
Algoritma pengurutan adaptive dalam prosesnya tidak akan melakukan pengurutan ulang pada elemen-elemen yang telah berada dalam urutan yang seharusnya. Sedangkan algoritma pengurutan non-adaptive tetap melakukan proses pengurutan pada elemen-elemen yang telah berada dalam urutan yang seharusnya untuk memastikan bahwa elemen-elemen tersebut memang berada pada urutan yang tepat.
Contoh Algoritma Pengurutan
Beberapa algoritma pengurutan yang sering digunakan diantaranya:
Insertion sort
Algoritma insertion sort adalah in-place dan adaptive algoritma. Insertion sort membandingkan nilai dari sebuah elemen dengan elemen-elemen berikutnya dalam satu orientasi tertentu, bisa dari kiri ke kanan atau sebaliknya. Pembandingan ini terus dilakukan dalam orientasi tersebut hingga elemen yang dibandingkan memenuhi sebuah syarat sepeti; elemen yang dibandingkan nilainya lebih besar atau nilainya lebih kecil dari elemen pembanding. Hal ini bertujuan untuk memastikan atau mengubah posisi sebuah elemen agar berada pada urutan yang tepat. Pengubahan posisi sebuah elemen hanya dilakukan jika element tersebut berada pada posisi yang salah. Proses ini dilakukan pada seluruh elemen hingga seluruh elemen berada pada posisi yang seharusnya.
Dalam python Insertion Sort dapat dituliskan dalam notasi berikut:
def InsertionSort(data):
for step in range(1, len(data)):
value = data[step]
i = step - 1
while i >= 0 and value < data[i]:
data[i + 1] = data[i]
i = i - 1
data[i + 1] = value
return data
data = [5, 4, 3, 2, 1]
result = InsertionSort(data)
print(result)Bubble sort
Proses pengurutan bubble sort dilakukan dengan membandingkan satu element dengan seluruh element. Perbandingan dilakukan baik dengan elemen yang terletak sebelum maupun setelahnya. Perbandingan dilakukan mulai dari elemen yang paling awal hingga yang paling akhir untuk menentukan urutan yang sesuai. Jika elemen yang dibandingkan memiliki nilai yang memenuhi sebuah kondisi sesuai orientasi yang diinginkan sepeti; elemen yang dibandingkan nilainya lebih besar atau nilainya lebih kecil dari elemen pembanding, maka posisi elemen tersebut ditukar.
Proses ini terus diulang hingga seluruh element telah dibandingkan dengan element lainnya dan setiap elemen berada di urutan yang bener
Dalam python Bubble Sort dapat dituliskan dalam notasi berikut:
def BubbleSort(data):
for step in range(len(data)):
for i in range(0, len(data) - step - 1):
if data[i] > data[i + 1]:
value = data[i]
data[i] = data[i+1]
data[i+1] = value
return data
data = [20, 50, 10, 40, 30]
result = BubbleSort(data)
print(result)Selections sort
Algoritma selection sort mencari nilai elemen yang paling kecil atau paling besar dan membandingkannya dengan seluruh elemen lainnya. Jika elemen yang dibandingkan menempati posisi yang salah, maka posisi elemen yang dibandingkan akan ditukar dengan elemen pembanding. Proses ini diulang hingga semua elemen menempati urutan yang sesuai.
Dalam python Selection Sort dapat dituliskan dalam notasi berikut:
def SelectionSort(data):
size = len(data)
for step in range(size):
min_idx = step
for i in range(step + 1, size):
if data[i] < data[min_idx]:
min_idx = i
(data[step], data[min_idx]) = (data[min_idx], data[step])
return data
data = [20, 50, 10, 40, 30]
result = SelectionSort(data)
print(result)Merge Sort
Proses penyelesaian merge sort dilakukan dengan membagi kumpulan elemen menjadi beberapa bagian dan memproses setiap bagian tersebut secara terpisah hingga mendapatkan hasil yang sesuai. Hasil dari setiap bagian-bagian tersebut lalu disatukan kembali hingga membentuk urutan elemen yang sesuai.
Dalam python Merge Sort dapat dituliskan dalam notasi berikut:
def MergeSort(data):
if len(data) > 1:
r = len(data)//2
L = data[:r]
M = data[r:]
MergeSort(L)
MergeSort(M)
i = j = k = 0
while i < len(L) and j < len(M):
if L[i] < M[j]:
data[k] = L[i]
i += 1
else:
data[k] = M[j]
j += 1
k += 1
while i < len(L):
data[k] = L[i]
i += 1
k += 1
while j < len(M):
data[k] = M[j]
j += 1
k += 1
return data
data = [20, 50, 10, 40, 30]
result = MergeSort(data)
print(result)Quick Sort
Pengurutan dilakukan dengan memilik satu elemen yang akan dijadikan sebagai pivot(poros). Setiap elemen lalu akan dibandingkan dengan elemen pivot ini dalam satu arah tertentu. Jika pivot mencapai sebuah element yang memiliki nilai lebih kecil dibandingkan dengan pivot maka, elemen tersebut akan bertukar tempat dengan elemen dengan nilai terbesar yang sebelumnya telah dibandingkan dengan pivot. Proses ini terus diulang hingga semua element menempati urutan yang sesuai
Dalam python Quick Sort dapat dituliskan dalam notasi berikut:
def Partition(data, low, high):
pivot = data[high]
i = low - 1
for j in range(low, high):
if data[j] <= pivot:
i = i + 1
(data[i], data[j]) = (data[j], data[i])
(data[i + 1], data[high]) = (data[high], data[i + 1])
return i + 1
def QuickSort(data, low, high):
if low < high:
pi = Partition(data, low, high)
QuickSort(data, low, pi - 1)
QuickSort(data, pi + 1, high)
return data
data = [70, 50, 20, 40, 10, 60, 30]
result = QuickSort(data, 0, len(data) - 1)
print(result)Referensi:
– https://www.tutorialspoint.com/data_structures_algorithms/sorting_algorithms.htm
– https://en.wikipedia.org/wiki/Sorting_algorithm#History_and_concepts
– https://en.wikipedia.org/wiki/Sorting
– https://www.programiz.com/dsa/algorithm
