Welcome To My Blog: Tugas Pertemuan 10 Algoritma

TUGAS KELOMPOK

Buatlah pengurutan dari data 29, 27, 10, 8, 76, 21 dengan metode sorting Selection Sort, Bubble Sort, Merge Sort, Quick Sort dan Insertion Sort.
Soal dikerjakan secara berkelompok dengan memberikan iterasi secara detail.

JAWAB :

Selection Sort
Data : 29, 27, 10, 8, 76, 21
Iterasi 1
1, 2, 3, 4, 5, 6
Langkah 1 : 29, 27, 10, 8, 76, 21
Langkah 2 : 29, 27, 10, 8, 76, 21
Langkah 3 : 8, 27, 10, 29, 76, 21
Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 2
Langkah 1 :   8, 27, 10,  29, 76, 21
Langkah 2 :   8, 27, 10,  29, 76, 21
Langkah 3 : 8, 10, 27, 29, 76, 21
Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 3
Langkah 1 : 8, 10, 27, 29, 76, 21
Langkah 2 : 8, 10, 27, 29, 76, 21
Langkah 3 : 8, 10, 21, 29, 76, 27
Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 4
Langkah 1   : 8, 10, 21, 29, 76, 27
Langkah 2 : 8, 10, 21, 29, 76, 27
Langkah 3 : 8, 10, 21, 27, 76, 29
Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 5
Langkah 1   :   8, 10, 21,  27, 76, 29
Langkah 2 : 8, 10, 21,  27, 76, 29
Langkah 3 : 8, 10, 21,  27, 29, 76
Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 6
Langkah 1   :   8, 10, 21,  27, 29, 76
Langkah 2 : 8, 10, 21,  27, 29, 76
Langkah 3 : 8, 10, 21,  27, 29, 76
Langkah 4 : Ulangi langkah 2 dan 3

Script #Selection Sort
def SelectionSort(val):
for i in range(len(val)-1,0,-1):
Max=0
for l in range(1,i+1):
if val[l]>val[Max]:
Max = l
temp = val[i]
val[i] = val[Max]
val[Max] = temp
Angka = [29,27,10,8,76,21]
SelectionSort(Angka)
print(Angka)

Program Dan Hasil RUN
Bubble Sort
Data : 29, 27, 10, 8, 76, 21
Iterasi 1
  1, 2, 3, 4, 5, 6
Langkah 1 : 29, 27, 10, 8, 76, 21
Langkah 2 : 29, 27, 10,   8, 21, 76
Langkah 3 : 29, 27, 10,   8, 21, 76
- 21>8, maka 21 tidak pindah,
untuk selanjutnya bandingkan data sebelumnya yaitu 8.
Langkah 4 : 29, 27, 8, 10, 21, 76
Langkah 5 : 29, 8, 27, 10, 21, 76
Langkah 5 : 8, 29,   27,  10, 21, 76
Langkah 6 : Ulangi langkah 2 dan 3

Iterasi 2
Langkah 1 :   8, 29,   27,  10,   21, 76
Langkah 2 :   8, 29,   27,  10,   21, 76
- 76>21, maka 76 tidak pindah,
untuk selanjutnya bandingkan data sebelumnya yaitu 21.
Langkah 3 :   8, 29,   27,  10,   21, 76
- 21>10, maka 21 tidak pindah,
untuk selanjutnya bandingkan data sebelumnya yaitu 10.
Langkah 4 :   8, 29,   27,  10,   21, 76
Langkah 5 :   8, 29,   10,  27,   21, 76
Langkah 6 :   8, 10,   29,  27,   21, 76
- 10>8, maka 10 tidak pindah.
Langkah 7 : Ulangi langkah 2 dan 3

Iterasi 3
Langkah 1 :   8, 10,   29,  27,   21, 76
Langkah 2 :   8, 10,   29,  27,   21, 76
- 76>21, maka 76 tidak pindah,
untuk selanjutnya bandingkan data sebelumnya yaitu 21.
Langkah 3 :   8, 10,   29,  27,   21, 76
Langkah 4 :   8, 10,   29,  21,   27, 76
Langkah 5 :   8, 10,   21,  29,   27, 76
- 21>10, maka 21 tidak pindah.
Langkah 6 : Ulangi langkah 2 dan 3

Iterasi 4
Langkah 1   : 8, 10,   21,  29,   27, 76
Langkah 2 : 8, 10,   21,  29,   27, 76
- 76>27, maka 76 tidak pindah,
untuk selanjutnya bandingkan data sebelumnya yaitu 27.
Langkah 3 : 8, 10,   21,  29,   27, 76
Langkah 4 : 8, 10,   21,  27,   29, 76
- 27>21, maka 27 tidak pindah.
Langkah 5 : Ulangi langkah 2 dan 3

Iterasi 5
Langkah 1   : 8, 10,   21,  27,   29, 76
Langkah 2 : 8, 10,   21,  27,   29, 76
- 76>29, maka 76 tidak pindah,
untuk selanjutnya bandingkan data sebelumnya yaitu 29.
Langkah 3 : 8, 10,   21,  27,   29, 76
- 29>27, maka 29 tidak pindah,
Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 6
Langkah 1   :   8, 10,   21,  27,   29, 76
Langkah 2 : 8, 10,   21,  27,   29, 76
- 76>29, maka 76 tidak pindah,
Langkah 3 : Ulangi langkah 2 dan 3

Script#Bubble Sort
def BubbleSort(X):
for i in range(len(X)-1,0,-1):
Max=0
for l in range(1,i+1):
if X[l]>X[Max]:
Max = l
temp = X[i]
X[i] = X[Max]
X[Max] = temp
Hasil = [29,27,10,8,76,21]
BubbleSort(Hasil)
print(Hasil)

Program Dan Hasil RUN
Quick Sort
Data : 29, 27, 10, 8, 76, 21
Iterasi 1   Pilih Vektor X => Elemen Pertama
29, 27, 10, 8, 76, 21
76
  29, 27, 10, 8, 21, 76

Iterasi 2   Pilih lagi Vektor X berikutnya
  29, 27, 10, 8, 21, 76
29
  27, 10, 8, 21, 29, 76

Iterasi 3   Pilih lagi Vektor X berikutnya
  27, 10, 8, 21, 29, 76
27
  10, 8, 21, 27, 29, 76

Iterasi 4   Pilih lagi Vektor X berikutnya
  10, 8, 21, 27, 29, 76
10
  8, 10, 21, 27, 29, 76

Script #Quick Sort
def partition(arr, low, high):
i = (low-1) # index of smaller element
pivot = arr[high] # pivot
for j in range(low, high):
if arr[j] <= pivot:
# increment index of smaller element
i = i+1
arr[i], arr[j] = arr[j], arr[i]

arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)
def quickSort(arr, low, high):
if len(arr) == 1:
return arr
if low < high:
pi = partition(arr, low, high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
# Driver code to test above
arr = [29, 27, 10, 8, 76, 21]
n = len(arr)
quickSort(arr, 0, n-1)
print("Sorted array is:")
for i in range(n):
print("%d" % arr[i]),

Program Dan Hasil RUN
Insertion Sort
Data : 29, 27, 10, 8, 76, 21
Iterasi 1
  1, 2, 3, 4, 5, 6
Langkah 1 : 29, 27, 10, 8, 76, 21
Langkah 2 : 29, 27, 10,   8, 76, 21
Langkah 3 : 27, 29, 10,   8, 76, 21
Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 2
Langkah 1 : 29, 27, 10, 8, 76, 21
Langkah 2 :  29,   27, 10,   8, 76, 21
Langkah 3 : 27, 29, 10,   8, 76, 21
Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 3
Langkah 1 : 27, 29, 10,   8, 76, 21
Langkah 2 : 27, 29, 10,   8, 76, 21
Langkah 3 : 10, 27, 29,   8, 76, 21
Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 4
Langkah 1 :  10, 27, 29,   8, 76, 21
Langkah 2 : 10, 27, 29,   8, 76, 21
Langkah 3 : 8, 10, 27, 29, 76, 21
Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 5
Langkah 1   :    8, 10, 27,  29, 76, 21
Langkah 2 :    8, 10, 27,  29, 76, 21
Langkah 3 :   8, 10, 27,  29, 76, 21
Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 6
Langkah 1   : 8, 10, 27,  29, 76, 21
Langkah 2 : 8, 10, 27,  29, 76, 21
Langkah 3 : 8, 10, 21,  27, 29, 76
Langkah 4 : Ulangi langkah 2 dan 3

Script #Insertion Sort
def InsertionSort(val):
for index in range(1,len(val)):
a = val[index]
b = index
while b>0 and val[b-1]>a:
val[b]=val[b-1]
b = b-1
val[b]=a

Angka = [29, 27, 10, 8, 76, 21]
InsertionSort(Angka)
print(Angka)

Program Dan Hasil RUN
Merge Sort
Data : 29, 27, 10, 8, 76, 21
Iterasi 1
  1, 2, 3, 4, 5, 6
Langkah 1 : 29, 27, 10, 8, 76, 21
Langkah 2 :  29, 27, 10, 8, 76, 21
Langkah 3 : 27, 29, 8,  10, 21, 76
Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 2
Langkah 1 :  27, 29,    8,  10, 21, 76
Langkah 2 :  27, 29,    8,  10, 21, 76
Langkah 3 :   8, 10,   27,  29, 21, 76
Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 3
Langkah 1 :   8,   10,   27,  29, 21, 76
Langkah 2 :   8,   10,   27,  29, 21, 76
Langkah 3 :    8,   10,   21,  27, 29, 76
Langkah 4 : Ulangi langkah 2 dan 3

Script #Merge Sort
def mergeSort(X):
print("Bilangan diurutkan ",X)
if len(X)>1:
mid = len(X)//2
lefthalf = X[:mid]
righthalf = X[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=j=k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
X[k]=lefthalf[i]
i=i+1
else:
X[k]=righthalf[j]
j=j+1
k=k+1
while i < len(lefthalf):
X[k]=lefthalf[i]
i=i+1
k=k+1
while j < len(righthalf):
X[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",X)

X = [29, 27, 10, 8, 76, 21]
mergeSort(X)
print(X)

Program Dan Hasil RUN