Metode-metode pengurutan data

Mata kuliah Struktur Data merupakan salah satu mata kuliah yang ajarkan pada banyak program studi ilmu komputer. Mata kuliah ini mempelajari struktur data dan algoritma diantaranya array, linked list, stack, queue, table hash, heap, metode pengurutan, metode pencarian, binary tree dan banyak lagi. Salah satu cara termudah memahami materi matakuliah ini adalah dengan cara memvisualisasikan materinya secara langsung, misalnya algoritma pengurutan. Tanpa visualisasi, algoritma pengurutan yang dipelajari harus dibayangkan oleh masing-masing orang.

Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)
Berikut metode pengurutan data :

• Bubble sort
  
• Shell sort
  
• Insertion sort
  
• Quick sort
  
• Radix sort
  
  Bubble Sort
  
  • Diberi nama "Bubble" karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda.
  
  
  • Bubble Sort mengurutkan data dengan cara
  membandingkan elemen sekarang dengan elemen berikutnya. Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
  
  Perhatikan bahwa jumlah pertukaran dan perbandingan data tidaklah tetap, perbedaan tergantung pada keadaan awal data setelah diacak. Tabel berikut memperlihatkan tabulasi hasil visualisasi menggunakan metode bubble sort.
  

  Pengacakan	Jumlah Total
  	Pertukaran Data	Perbandingan Data
  1	155	279
  2	127	272
  3	137	245
  4	142	297
  5	151	294
  6	138	285
  7	178	300
  8	165	272
  9	156	285
  10	175	300
  Rata-rata	152	283

  Jumlah rata-rata pertukaran untuk 10 kali pengacakan adalah 152 kali, sedangkan rata-rata jumlah perbandingan adalah sebanyak 283 kali. Tetapi bila data pada awalnya terurut, maka untuk 25 jumlah data, jumlah pertukaran data sebanyak 0 kali dengan jumlah perbandingan sebanyak 24 kali.
  
  Shell Sort
  
  • Dikembangkan oleh Donald L. Shell (1959)
  • Mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu sehingga dibentuk sub-list, kemudian dilakukanZ pertukaran jika diperlukan
  
  Jumlah pertukaran data dengan metode ini tidak selalu tetap namun tergantung pada keadaan awal data. Sedangkan jumlah perbandingan data selalu tetap. Tabel berikut memperlihatkan tabulasi hasil visualisasi menggunakan metode selection sort.
  

  Pengacakan	Jumlah Total
  	Pertukaran Data	Perbandingan Data
  1	23	325
  2	24	325
  3	21	325
  4	22	325
  5	23	325
  6	22	325
  7	21	325
  8	20	325
  9	23	325
  10	22	325
  Rata-rata	22	325

  Terlihat bahwa jumlah pertukaran data turun drastis dibandingkan pengurutan menggunakan metode bubble sort, karena memang metode selection sort diciptakan untuk memperbaiki metode bubble sort mengurangi jumlah perbandingan [4]. Jumlah perbandingan data selalu tetap dan tidak tergantung pada keadaan awal data. Bila data awal dalam keadaan sudah terurut, maka untuk jumlah data yang sama, total pertukaran data sebanyak 0 kali dengan jumlah perbandingan tetap 325 kali.
  
  Metode Insertion Sort
  
  Hasil pengamatan menunjukkan bahwa dengan jumlah data dan jumlah pengacakan yang sama, metode insertion sort bekerja lebih cepat dibandingkan dengan metode bubble sort dan selection sort (untuk mencatat waktu secara lebih tepat, mungkin program perlu dimodifikasi sehingga waktu proses pengurutan dapat dihitung secara tepat). Jumlah pertukaran data dengan metode ini juga tergantung pada keadaan awal data yaitu rata-rata sebanyak 136 kali (dari 10 kali pengamatan), dan jumlah perbandingan data selalu 300 kali. Berikut tabulasi hasil visualisasi menggunakan metode insertion sort.
  

  Pengacakan	Jumlah Total
  	Pertukaran Data	Perbandingan Data
  1	149	300
  2	138	300
  3	168	300
  4	157	300
  5	102	300
  6	106	300
  7	122	300
  8	123	300
  9	145	300
  10	148	300
  Rata-rata	136	300

  Berikut contohnya
  
  #include <conio.h>
  #include <stdio.h>
  #include <iostream.h>
  
  void main ()
  {
  char nama[20];
  char jurusan [20];
  cout<<"masukkan nama anda: ";cin.getline(nama,20);
  cout<<"masukkan jurusan anda: ";cin.getline(jurusan,20);
  cout<<"nama anda: "<<nama<<endl;
  cout<<"jurusan anda: "<<jurusan;
  getch();
  }