Algoritma Sorting Quick Sort

Nama       : Zania Abuk Da Costa

NIM         : 201552018152957

Jurusan    : Teknik Informatika 

Quick Sort

Algoritma quick sort ini cara kerjanya berprinsip pada penekatan divide and conquer yakni dengan memilih satu elemen sebagai elemen pivot dan mempartisi array sehingga sisi kiri pada pivot mempunyai semua elemen dengan nilai yang lebih kecil dibandingkan dengan elmen pivot dan pada sisi kanan mempunyai semua elemen dengan nilai yang lebih besar dibandingkan dengan nilai elemen pivot.

Analogi algoritma quick sort :

• Mempunyai data A yang memiliki N elemen, pilih sembarang elemen dari data tersebut biasanya        elemen pertama misalkan elemen x
• Kemudian semua elemen tersebut disusun dengan menempatkan x pada posisi j sedemikian rupa sehingga elemen ke satu sampai pada j-1 dan memiliki nilai yang lebih besar dari x
• Begitu seterusnya setiap sub data

01	def qs(list,awal,akhir):

02	if awal < akhir:

03	pindex = partisi(list,awal,akhir)

04	qs(list,awal,pindex-1)

05	qs(list,pindex+1,akhir)

06

07	def partisi(list,awal,akhir):

08	tengah = int(akhir/2)

09	pivot = list[tengah]

10	pindex = awal

11	for i in range(awal,tengah):

12	if list[i]>=pivot:

13	list[i],list[pindex]=list[pindex],list[i]

14	pindex = pindex + 1

15	list[pindex],list[tengah]=list[tengah],list[pindex]

16	print(list)

17	return pindex

18

19	list = [67,91,87,33,49,10,16,43,65,3]

20	print('Data yang akan di sort :', list)

21	print('Quick Sort :')

22	qs(list,0,len(list)-1)

Output dari penerapan quick sort di atas seperti pada gambar di bawah ini :

Output Quick Sort