Install Web App

BRIEF

MINA

Python Lanjutan

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

profil-penulis

Robert Saputra

20 Maret 2023

Partitioning adalah salah satu langkah penting dalam algoritma Quick Sort yang digunakan untuk membagi daftar menjadi dua bagian: elemen-elemen yang lebih kecil dari pivot (elemen pembanding) dan elemen-elemen yang lebih besar dari pivot. Dalam artikel ini, kita akan menjelaskan cara melakukan partitioning dengan pivot dalam bahasa pemrograman Python.

Langkah-langkah Partitioning dengan Pivot:

Langkah-langkah berikut menjelaskan bagaimana partitioning dengan pivot dilakukan:

  1. Pilih Pivot: Pilih salah satu elemen dalam daftar sebagai pivot. Pilihan pivot dapat bervariasi, seperti memilih elemen pertama, elemen terakhir, elemen tengah, atau bahkan secara acak. Pemilihan pivot yang baik dapat memengaruhi kinerja algoritma Quick Sort.

  2. Inisialisasi Pointer: Inisialisasi dua pointer, yaitu left dan right. Pointer left menunjuk ke elemen pertama dalam daftar, dan pointer right menunjuk ke elemen terakhir dalam daftar.

  3. Partisi: Mulailah proses partisi dengan cara membandingkan elemen di left dengan pivot dan elemen di right dengan pivot. Langkah-langkahnya sebagai berikut:

    a. Geser pointer left ke kanan sampai menemukan elemen yang lebih besar atau sama dengan pivot.

    b. Geser pointer right ke kiri sampai menemukan elemen yang lebih kecil atau sama dengan pivot.

    c. Jika pointer left masih kurang dari atau sama dengan pointer right, tukar elemen di left dengan elemen di right.

    d. Ulangi langkah-langkah di atas hingga pointer left lebih besar dari pointer right.

  4. Tukar Pivot: Setelah pointer left lebih besar dari pointer right, tukar pivot dengan elemen di left. Sekarang, semua elemen yang lebih kecil dari pivot berada di sebelah kiri pivot, dan elemen-elemen yang lebih besar berada di sebelah kanan.

  5. Kembalikan Pivot Index: Kembalikan indeks pivot sebagai hasil dari proses partisi. Indeks pivot ini akan digunakan untuk membagi daftar menjadi dua bagian selama proses Quick Sort.

Implementasi Partitioning dengan Pivot dalam Python:

Berikut adalah contoh implementasi partitioning dengan pivot dalam Python:

def partition(arr, low, high):
    pivot = arr[high]  # Pilih pivot (dalam contoh ini, elemen terakhir)
    i = low - 1  # Inisialisasi indeks i yang awalnya di luar daftar

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # Tukar elemen

    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # Tukar pivot dengan elemen di i+1
    return i + 1  # Kembalikan indeks pivot

# Contoh penggunaan
data = [64, 34, 25, 12, 22, 11, 90]
pivot_index = partition(data, 0, len(data) - 1)
print("Hasil setelah partisi:", data)
print("Indeks pivot:", pivot_index)

Dalam implementasi di atas, kita memilih elemen terakhir sebagai pivot. Kemudian, kita menggunakan dua pointer, yaitu i dan j, untuk membandingkan elemen-elemen dengan pivot. Selama proses partisi, elemen-elemen yang lebih kecil dari pivot akan dipindahkan ke sebelah kiri, dan elemen-elemen yang lebih besar akan tetap di sebelah kanan. Setelah selesai, pivot akan ditukar dengan elemen di indeks i + 1, dan hasilnya adalah daftar yang terbagi menjadi dua bagian dengan pivot di posisi yang benar.

 

Partitioning dengan pivot adalah langkah kunci dalam algoritma Quick Sort yang membagi daftar menjadi dua bagian. Ini adalah salah satu langkah yang memungkinkan Quick Sort untuk mengurutkan elemen-elemen dengan efisien. Dalam Python, implementasi partitioning dengan pivot seperti yang ditunjukkan dalam contoh di atas dapat digunakan sebagai bagian dari algoritma Quick Sort.

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