Mengurutkan Implementasi Algoritma dengan Python

Sorting adalah salah satu fitur yang paling banyak digunakan dalam pemrograman. Dan butuh waktu untuk menyelesaikan penyortiran jika kami tidak menggunakan algoritme yang benar.

Pada artikel ini, kita akan membahas algoritma pengurutan yang berbeda.

Kami akan memandu Anda melalui algoritme penyortiran yang berbeda dengan setiap langkah yang diterapkan. Bagian implementasi akan menggunakan Python. Anda dapat dengan mudah mengubahnya menjadi bahasa apa pun setelah Anda mendapatkan algoritme. Itu soal sintaks bahasa.

Kita akan melihat berbagai algoritme dari yang terburuk hingga yang terbaik dalam tutorial ini. Jadi, jangan khawatir. Ikuti artikelnya dan terapkan.

Mari selami algoritma pengurutan.

Sortir Penyisipan

Insertion sort adalah salah satu algoritma sorting sederhana. Mudah diterapkan. Dan itu akan menghabiskan lebih banyak waktu untuk mengurutkan array. Itu tidak akan digunakan di sebagian besar kasus untuk menyortir array yang lebih besar.

Algoritma penyisipan mempertahankan sub-bagian yang diurutkan dan tidak disortir dalam larik yang diberikan.

Sub-bagian yang diurutkan hanya berisi elemen pertama pada awal proses penyortiran. Kami akan mengambil elemen dari array yang tidak disortir dan menempatkannya di posisi yang benar di sub-array yang diurutkan.

Mari kita lihat ilustrasi visual insertion sort langkah demi langkah dengan sebuah contoh.

Mari kita lihat langkah-langkah untuk mengimplementasikan insertion sort.

  • Inisialisasi array dengan data dummy (bilangan bulat).
  • Ulangi array yang diberikan dari elemen kedua.
    • Ambil posisi dan elemen saat ini dalam dua variabel.
    • Tulis sebuah loop yang berulang sampai elemen pertama dari array atau elemen terjadi yang kurang dari elemen saat ini.
      • Perbarui elemen saat ini dengan elemen sebelumnya.
      • Penurunan posisi saat ini.
    • Di sini, perulangan harus mencapai awal larik atau menemukan elemen yang lebih kecil dari elemen saat ini. Ganti elemen posisi saat ini dengan elemen saat ini.

Kompleksitas waktu dari urutan penyisipan adalah O(n^2), dan kompleksitas ruang jika O(1).

  Cara Mengubah Negara Atau Wilayah Untuk ID Apple Anda

Itu dia; kami telah mengurutkan array yang diberikan. Mari jalankan kode berikut. Saya harap Anda telah menginstal Python, jika tidak lihat panduan instalasi. Atau, Anda dapat menggunakan kompiler Python online.

def insertion_sort(arr, n):
	for i in range(1, n):

		## current position and element
		current_position = i
		current_element = arr[i]

		## iteratin until
		### it reaches the first element or
		### the current element is smaller than the previous element
		while current_position > 0 and current_element <
		 arr[current_position - 1]:
			## updating the current element with previous element
			arr[current_position] = arr[current_position - 1]

			## moving to the previous position
			current_position -= 1

		## updating the current position element
		arr[current_position] = current_element

if __name__ == '__main__':
	## array initialization
	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
	insertion_sort(arr, 9)

	## printing the array
	print(str(arr))

Sortir Seleksi

Seleksi pemilihan mirip dengan jenis penyisipan dengan sedikit perbedaan. Algoritma ini juga membagi array menjadi sub-bagian yang disortir dan tidak disortir. Kemudian, pada setiap iterasi, kita akan mengambil elemen minimum dari sub-bagian yang tidak disortir dan menempatkannya di posisi terakhir dari sub-bagian yang diurutkan.

Mari ilustrasikan jenis seleksi untuk pemahaman yang lebih baik.

Mari kita lihat langkah-langkah untuk mengimplementasikan sortasi pilihan.

  • Inisialisasi array dengan data dummy (bilangan bulat).
  • Ulangi array yang diberikan.
    • Pertahankan indeks elemen minimum.
    • Tulis sebuah loop yang beriterasi dari elemen saat ini ke elemen terakhir.
      • Periksa apakah elemen saat ini kurang dari elemen minimum atau tidak.
      • Jika elemen saat ini kurang dari elemen minimum, ganti indeks.
    • Kami memiliki indeks elemen minimum bersama kami. Tukar elemen saat ini dengan elemen minimum menggunakan indeks.

Kompleksitas waktu dari urutan seleksi adalah O(n^2), dan kompleksitas ruang jika O(1).

Coba terapkan algoritme karena mirip dengan pengurutan penyisipan. Anda dapat melihat kode di bawah ini.

def selection_sort(arr, n):
	for i in range(n):

		## to store the index of the minimum element
		min_element_index = i
		for j in range(i + 1, n):
			## checking and replacing the minimum element index
			if arr[j] < arr[min_element_index]:
				min_element_index = j

		## swaping the current element with minimum element
		arr[i], arr[min_element_index] = arr[min_element_index], arr[i]

if __name__ == '__main__':
	## array initialization
	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
	selection_sort(arr, 9)

	## printing the array
	print(str(arr))

Sortir Gelembung

Bubble sort adalah algoritma sederhana. Itu menukar elemen yang berdekatan pada setiap iterasi berulang kali hingga array yang diberikan diurutkan.

  Cara Mengaktifkan Tombol Putar/Jeda di Bilah Alat Chrome

Iterate atas array dan memindahkan elemen saat ini ke posisi berikutnya sampai kurang dari elemen berikutnya.

Ilustrasi membantu kita memahami pengurutan gelembung secara visual. Mari kita lihat mereka.

Mari kita lihat langkah-langkah untuk mengimplementasikan bubble sort.

  • Inisialisasi array dengan data dummy (bilangan bulat).
  • Ulangi array yang diberikan.
  • Ulangi dari 0 hingga ni-1. Elemen i terakhir sudah diurutkan.
  • Periksa apakah elemen saat ini lebih besar dari elemen berikutnya atau tidak.
  • Jika elemen saat ini lebih besar dari elemen berikutnya, maka tukar kedua elemen tersebut.
  • Kompleksitas waktu dari bubble sort adalah O(n^2), dan kompleksitas ruang jika O(1).

    Anda dapat dengan mudah mengimplementasikan bubble sort sekarang. Mari kita lihat kodenya.

    def bubble_sort(arr, n):
    	for i in range(n):
    		## iterating from 0 to n-i-1 as last i elements are already sorted
    		for j in range(n - i - 1):
    			## checking the next element
    			if arr[j] > arr[j + 1]:
    				## swapping the adjucent elements
    				arr[j], arr[j + 1] = arr[j + 1], arr[j]
    
    if __name__ == '__main__':
    	## array initialization
    	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
    	bubble_sort(arr, 9)
    
    	## printing the array
    	print(str(arr))

    Gabungkan Sortir

    Merge sort adalah algoritma rekursif untuk mengurutkan array yang diberikan. Ini lebih efisien daripada algoritma yang dibahas sebelumnya dalam hal kompleksitas waktu. Ini mengikuti pendekatan membagi dan menaklukkan.

    Algoritme sortir gabungan membagi array menjadi dua bagian dan mengurutkannya secara terpisah. Setelah menyortir dua bagian dari array, itu menggabungkannya menjadi satu array yang diurutkan.

    Karena ini adalah algoritme rekursif, ia membagi array hingga array menjadi yang paling sederhana (array dengan satu elemen) untuk diurutkan.

    Saatnya ilustrasi. Mari kita lihat.

    Mari kita lihat langkah-langkah untuk menerapkan jenis gabungan.

    • Inisialisasi array dengan data dummy (bilangan bulat).
    • Tulis fungsi yang disebut gabung untuk menggabungkan sub-array menjadi satu larik yang diurutkan. Ia menerima array argumen, indeks kiri, tengah, dan kanan.
      • Dapatkan panjang sub-array kiri dan kanan menggunakan indeks yang diberikan.
      • Salin elemen dari larik ke larik kiri dan kanan masing-masing.
      • Ulangi dua sub-array.
        • Bandingkan dua elemen sub-array.
        • Ganti elemen array dengan elemen yang lebih kecil dari dua sub-array untuk penyortiran.
      • Periksa apakah ada elemen yang tersisa di kedua sub-array.
      • Tambahkan mereka ke array.
    • Tulis fungsi yang disebut merge_sort dengan array parameter, indeks kiri dan kanan.
      • Jika indeks kiri lebih besar dari atau sama dengan indeks kanan, maka kembalikan.
      • Temukan titik tengah larik untuk membagi larik menjadi dua bagian.
      • Secara rekursif panggil merge_sort menggunakan indeks kiri, kanan, dan tengah.
      • Setelah panggilan rekursif, gabungkan array dengan fungsi gabungan.
      Cara Mengelola Data yang Dikumpulkan LinkedIn tentang Anda

    Kompleksitas waktu dari jenis gabungan adalah O(nlogn), dan kompleksitas ruang jika O(1).

    Itu saja untuk implementasi algoritma sortir gabungan. Periksa kode di bawah ini.

    def merge(arr, left_index, mid_index, right_index):
    	## left and right arrays
    	left_array = arr[left_index:mid_index+1]
    	right_array = arr[mid_index+1:right_index+1]
    
    	## getting the left and right array lengths
    	left_array_length = mid_index - left_index + 1
    	right_array_length = right_index - mid_index
    
    	## indexes for merging two arrays
    	i = j = 0
    
    	## index for array elements replacement
    	k = left_index
    
    	## iterating over the two sub-arrays
    	while i < left_array_length and j < right_array_length:
    
    		## comapring the elements from left and right arrays
    		if left_array[i] < right_array[j]:
    			arr[k] = left_array[i]
    			i += 1
    		else:
    			arr[k] = right_array[j]
    			j += 1
    		k += 1
    
    	## adding remaining elements from the left and right arrays
    	while i < left_array_length:
    		arr[k] = left_array[i]
    		i += 1
    		k += 1
    
    	while j < right_array_length:
    		j += 1
    		k += 1
    
    def merge_sort(arr, left_index, right_index):
    	## base case for recursive function
    	if left_index >= right_index:
    		return
    
    	## finding the middle index
    	mid_index = (left_index + right_index) // 2
    
    	## recursive calls
    	merge_sort(arr, left_index, mid_index)
    	merge_sort(arr, mid_index + 1, right_index)
    
    	## merging the two sub-arrays
    	merge(arr, left_index, mid_index, right_index)
    
    if __name__ == '__main__':
    	## array initialization
    	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
    	merge_sort(arr, 0, 8)
    
    	## printing the array
    	print(str(arr))

    Kesimpulan

    Ada banyak algoritma pengurutan lainnya, tetapi di atas adalah beberapa yang sering digunakan. Harap Anda menikmati belajar menyortir.

    Selanjutnya, cari tahu tentang algoritma pencarian.

    Selamat Coding 🙂 👨‍💻