Install Web App

BRIEF

MINA

Python Lanjutan

Belajar Algoritma & Struktur Data Python #18 |Merge Sort - Concept 2

profil-penulis

Edo Kurniawan

20 Maret 2023

Merge Sort adalah salah satu algoritma pengurutan yang efisien dan stabil yang digunakan untuk mengurutkan elemen dalam daftar atau array. Algoritma ini bekerja dengan cara membagi daftar menjadi dua bagian, mengurutkan masing-masing bagian secara terpisah, dan kemudian menggabungkan kembali dua bagian yang sudah terurut menjadi satu. Dalam artikel ini, kita akan membahas konsep dasar Merge Sort dan bagaimana melakukan penggabungan (merging) dua daftar terurut, yang merupakan fondasi dari konsep Merge Sort dalam bahasa pemrograman Python.

Prinsip Dasar Merge Sort:

Prinsip dasar dari Merge Sort adalah membagi daftar menjadi dua bagian secara rekursif hingga masing-masing bagian hanya memiliki satu elemen atau kosong. Setelah itu, dua bagian yang terpisah digabungkan kembali secara berurutan, sehingga seluruh daftar terurut.

Langkah-langkah Merging Dua Daftar Terurut:

Penggabungan (merging) dua daftar terurut merupakan langkah penting dalam Merge Sort. Berikut adalah langkah-langkah untuk melakukan merging dua daftar terurut:

  1. Bandingkan Elemen Pertama: Bandingkan elemen pertama dari kedua daftar.

  2. Pilih Elemen Terkecil: Pilih elemen yang lebih kecil dari kedua elemen yang dibandingkan dan masukkan ke dalam daftar hasil.

  3. Geser Indeks: Geser indeks di daftar yang memiliki elemen terkecil untuk menunjuk elemen berikutnya.

  4. Ulangi Proses: Ulangi langkah-langkah di atas hingga salah satu dari kedua daftar terurut habis.

  5. Tambahkan Elemen Sisa: Setelah salah satu daftar terurut habis, tambahkan semua elemen sisa dari daftar lainnya ke daftar hasil, karena elemen-elemen tersebut sudah terurut.

Implementasi Merging Dua Daftar Terurut dalam Python:

Berikut adalah contoh implementasi merging dua daftar terurut dalam Python:

def merge(left, right):
    result = []  # Daftar hasil penggabungan
    i = j = 0  # Indeks untuk daftar kiri dan kanan
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # Tambahkan sisa elemen dari kedua daftar
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# Contoh penggunaan
left_list = [1, 3, 5, 7]
right_list = [2, 4, 6, 8]
merged_list = merge(left_list, right_list)
print("Hasil penggabungan:", merged_list)

Dalam implementasi di atas, fungsi merge menerima dua daftar terurut (left dan right) sebagai input dan mengembalikan daftar hasil dari penggabungan kedua daftar tersebut.

Contoh Pengaplikasian Merge Sort:

Mari kita lihat contoh penggunaan Merge Sort untuk mengurutkan daftar angka dari kecil ke besar:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    
    return merge(left_half, right_half)

data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = merge_sort(data)
print("Hasil setelah Merge Sort:", sorted_data)

Dalam contoh ini, kita menggunakan fungsi merge_sort yang secara rekursif membagi daftar menjadi dua bagian, mengurutkan masing-masing bagian, dan kemudian menggabungkan kembali dua bagian tersebut.

Kesimpulan: Merging dua daftar terkita menggunakan fungsi merge_sort yang secara rekursif membagi daftar menjadi dua bagian, mengurutkan masing-masing bagian, dan kemudian menggabungkan kembali dua bagian tersebut.urut adalah langkah penting dalam konsep Merge Sort. Algoritma ini bekerja dengan membagi, mengurutkan, dan menggabungkan kembali bagian-bagian daftar. Meskipun lebih kompleks daripada algoritma pengurutan sederhana, Merge Sort memiliki kinerja yang baik dan digunakan dalam berbagai aplikasi yang memerlukan pengurutan data.

Artikel Lainnya Dengan Kategori Terkait :

1. Belajar Algoritma & Struktur Data Python #01 |Apa itu Algoritma

2. Belajar Algoritma & Struktur Data Python #02 |Representasi dan Perencanaan Algoritma - Pseudocode

3. Belajar Algoritma & Struktur Data Python #03 |contoh Pseudocode

4. Belajar Algoritma & Struktur Data Python #04 |Apa itu Struktur Data

5. Belajar Algoritma & Struktur Data Python #05 |Searching Algorithm Sequential vs Binary

6. Belajar Algoritma & Struktur Data Python #07 |Binary Search - Definition

7. Belajar Algoritma & Struktur Data Python #08 |Sequential Search - Definition

8. Belajar Algoritma & Struktur Data Python #09 |Sequential Search - Python Implementation

9. Belajar Algoritma & Struktur Data Python #10 |Sorting Algorithm

10. Belajar Algoritma & Struktur Data Python #11 |Bubble Sort - Concept

11. Belajar Algoritma & Struktur Data Python #12 |Bubble Sort - Python Implementation

12. Belajar Algoritma & Struktur Data Python #13 |Selection Sort - Concept

13. Belajar Algoritma & Struktur Data Python #14 |Selection Sort - Python Implementation

14. Belajar Algoritma & Struktur Data Python #15 |Insertion Sort - Concept

15. Belajar Algoritma & Struktur Data Python #16 |Insertion Sort - Python Implementation

16. Belajar Algoritma & Struktur Data Python #17 |Merge Sort - Concept - 1

17. Belajar Algoritma & Struktur Data Python #18 |Merge Sort - Concept 2

18. Belajar Algoritma & Struktur Data Python #19 |Merge Sort - Python Implementation

19. Belajar Algoritma & Struktur Data Python #20 |Quick Sort - Concept 1

20. Belajar Algoritma & Struktur Data Python #21 |Quick Sort - Concept 2

21. Belajar Algoritma & Struktur Data Python #22 |Quick Sort - Python Implementation

22. Belajar Algoritma & Struktur Data Python #23 |Selection Sort - Concept

23. Belajar Algoritma & Struktur Data Python #24 |Apa itu Stack

24. Belajar Algoritma & Struktur Data Python #25 |Stack - Python Implementation

25. Belajar Algoritma & Struktur Data Python #26 |Apa itu Queue

26. Belajar Algoritma & Struktur Data Python #27 |Queue - Python Implementation

27. Belajar Algoritma & Struktur Data Python #28 |Apa itu Hash Table

28. Belajar Algoritma & Struktur Data Python #29 |Konsep Hashing

29. Belajar Algoritma & Struktur Data Python #30 |Mendeklarasikan Hash Table sebagai classcar

30. Belajar Algoritma & Struktur Data Python #31 |Mengimplementasikan Hash Table

31. Belajar Python Lanjutan #01 |Function - Basic Structure

32. Belajar Python Lanjutan #02 |Function - Call a Function

33. Belajar Python Lanjutan #03 |Function - Arguments and Parameters

34. Belajar Python Lanjutan #04 |Function - Arbitrary Arguments

35. Belajar Python Lanjutan #05 |Default Parameters

36. Belajar Python Lanjutan #06 |Default Parameters in Multiple Parameters

37. Belajar Python Lanjutan #07 |Set - Difference Of Set

38. Belajar Python Lanjutan #08 |Function - Keyword Parameter

39. Belajar Python Lanjutan #09 |Function - Return Statement

40. Belajar Python Lanjutan #10 |Recursive Function

41. Belajar Python Lanjutan #11 |Lambda - Expression and Syntax

42. Belajar Python Lanjutan #12 |Lambda - Filter

43. Belajar Python Lanjutan #13 |Lambda - Map

44. Belajar Python Lanjutan #14 |Lambda - Reduce

45. Belajar Python Lanjutan #15 |Nested Function Concept

46. Belajar Python Lanjutan #16 |Default Parameters in Multiple Parameters

47. Belajar Python Lanjutan #17 |Non-local Variable - Local Variable vs Global Variable

48. Belajar Python Lanjutan #18 |Closure - Concept

49. Belajar Python Lanjutan #19 |Class - Definition and Concept of Object

50. Belajar Python Lanjutan #20 |Class - Instances vs Class

51. Belajar Python Lanjutan #21 |Class - Declaring and Self Parameters

52. Belajar Python Lanjutan #22 |Class - Constructor init Method

53. Belajar Python Lanjutan #23 |Instance Variables

54. Belajar Python Lanjutan #24 |Class Variables

55. Belajar Python Lanjutan #25 |Class - Inheritence

56. Belajar Python Lanjutan #26 |Default Parameters in Multiple Parameters

57. Belajar Python Lanjutan #27 |Class - Polymorphism

58. Belajar Python Lanjutan #28 |Class - Encapsulation

59. Belajar Python Lanjutan #29 |Class - Abstraction

60. Belajar Python Lanjutan #30 |Apa itu Concurrency dan Parallelism

61. Belajar Python Lanjutan #31 |threading

62. Belajar Python Lanjutan #32 |library threading

63. Belajar Python Lanjutan #33 |Multiprocessing

64. Belajar Python Lanjutan #34 |Implementasi library multiprocessing

65. Belajar Python Lanjutan #35 |Kemiripan multiprocessing dengan threading

Masuk Terlebih dahulu untuk berkomentar

Paling baru
Lihat Lainnya