Insertion Sort dan Quick Sort

SORTING II

Insertion Sort
Prinsip algoritma insertion sort pada dasarnya membagi data yang akan diurutkan menjadi dua bagian, satu bagian yang belum diurutkan dan yang satunya lagi sudah diurutkan. Elemen pertama diambil dari bagian list yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari list yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian list yang belum diurutkan.
Langkahnya seperti di bawah ini :

1.      Bandingkan data ke-2 dengan data ke-1, jika data ke-2 lebih kecil maka tukar posisinya, jika tidak biarkan aja.

2.      Data ke-3 dibandingkan dengan data ke-1 dan ke-2, jika data ke-3 lebih kecil kemudian tukar lagi posisinya.

3.      Data ke-4 dibandingkan dengan data ke-3, ke-2, dan ke-1, jika data ke-4 lebih kecil dari ketiganya maka letakkan data ke-4 ke posisi paling depan. Begitu seterusnya sampai tidak ada lagi data yang bisa dipindahkan.

 

Kode Programnya

Quick Sort

Quick sort adalah algoritma sorting yang beradasarkan pembandingan dan quick sort ini mengurutkkan dengan sangat cepat. Pengurutan Quick sort di tentukan oleh pivot dan pivot tersebut bisa di depan , belakang dan tengah. namun algoritma ini sangat komplex dan diproses secara rekursif. Tetapi langkah pengerjaanya rumit.

Kode Programnya

 

Doubly Linked List

Doubly Linked List 

Doubly Linked List sama seperti Singly link list merupakan sebuah tempat yang disediakan pada satu area memori tertentu untuk menyimpan data yang dikenal dengan sebutan node atau simpul. Akan tetapi, setiap node pada doubly linked list selain memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, juga memiliki pointer yang menunjuk ke simpul sebelumnya. Susunan berupa untaian model ini disebut Doubly Linked List. 

Kode Programnya:

# Class Node

class Node(object):

    # Inisialisasi node

    def __init__(self, data, prev, next):

        self.data = data

        self.prev = prev

        self.next = next

# Class untuk linked list

class DoubleList(object):

    head = None

    tail = None        

    # Menambah node

    def menuTambah(self):

        os.system('clear')

        temp = int(input('Masukkan data baru = '))

        new_node = Node(temp, None, None)

        # Memeriksa apakah list kosong

        if self.head is None:

            # Menunjuk HEAD dan TAIL ke node baru

            self.head = self.tail = new_node

        # Ketika list tidak kosong

        else:

            new_node.prev = self.tail

            new_node.next = None

            self.tail.next = new_node

            self.tail = new_node

   

    # Menghapus node

    def menuHapus(self):

        os.system('clear')

        temp = int(input('Masukkan data yang akan dihapus = '))

        # Membuat pointer yang menunjuk ke node pertama

        current_node = self.head

       

        # Melakukan perulangan saat list tidak kosong

        while current_node is not None:

            # Memeriksa data pada node yang ditunjuk pointer merupakan node yang akan dihapus

            if current_node.data == temp:

                #jika node yang dicari berada pada elemen terakhir

                if current_node.next is None:

                    current_node.prev.next = None

                # jika node yang dicari berada bukan pada elemen pertama

                elif current_node.prev is not None:

                    current_node.prev.next = current_node.next

                    current_node.next.prev = current_node.prev

                # Jika node yang dicari berada pada elemen pertama

                else:

                    self.head = current_node.next #memindahkan head ke elemen berikutnya

                    current_node.next.prev = None #menunjuk head prev menjadi none

            # Memindahkan pointer menunjuk ke node berikutnya

            current_node = current_node.next

           

    # Menampilkan isi dari list    

    def menuTampil(self):

        os.system('clear')

        print ("Tampilkan list data:")

       

        # Membuat pointer yang menunjuk ke node pertama

        current_node = self.head

        # Perulangan menampilkan data beserta data sebelum dan sesudahnya

        while current_node is not None:

            print (current_node.prev.data) if hasattr(current_node.prev, "data") else None,

            print (current_node.data),

            print (current_node.next.data) if hasattr(current_node.next, "data") else None

            # Menunjuk ke node berikutnya

            current_node = current_node.next

           

    # Menampilkan menu program     

    def menuUmum(self):

        pilih = "y"

        while ((pilih == "y") or (pilih == "Y")):

            os.system('clear')

            print('Pilih menu yang anda inginkan')

            print('==============================')

            print('1 : Tambah data ke linked list')

            print('2 : Hapus data di linked list')

            print('3 : Tampilkan data di linked list')

            print('4 : Keluar Program')

            pilihan = str(input("Masukkan Menu yang anda pilih = "))

            if(pilihan == "1"):

                self.menuTambah()

            elif(pilihan == "2"):

                self.menuHapus()

            elif(pilihan == "3"):

                self.menuTampil()

                x = input("")

            else :

                pilih ="n"

               

if __name__ == "__main__":

    # execute only if run as a script

    d = DoubleList()

    d.menuUmum()

Single Link List

 Linked list

Linked list merupakan sebuah data yang saling berkaitan satu sama lain. Sehingga dapat kita analaogikan sebagai tali yang memiliki sebuah data.

Single Linked List merupakan sebuah tempat yang disediakan pada satu area memori tertentu untuk menyimpan data yang dikenal dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List. Biasanya Linked List pada node terakhir akan menunjuk ke NULL, dimana  NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana.

Pembuatan Single Linked List dapat menggunakan 2 metode:

– LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)

– FIFO (First In First Out), aplikasinya : Queue (Antrean)

Kode Program:

#Ordered List mengurutkan data dari terkecil ke terbesar

class Node:

  def __init__(self,initdata):

    self.data = initdata

    self.next = None

  def getData(self):

    return self.data

  def getNext(self):

    return self.next

  def setData(self,newdata):

    self.data = newdata

  def setNext(self,newnext):

    self.next = newnext

   

class OrderedList:

    def __init__(self):

        self.head = None

    def search(self,item):

        current = self.head

        found = False

        stop = False

        while current != None and not found and not stop:

            if current.getData() == item:

                found = True

            else:

                if current.getData() > item:

                    stop = True

                else:

                    current = current.getNext()

        return found

    def add(self,item):

        current = self.head

        previous = None

        stop = False

        while current != None and not stop:

            if current.getData() < item:

                stop = True

            else:

                previous = current

                current = current.getNext()

        temp = Node(item)

        if previous == None:

            temp.setNext(self.head)

            self.head = temp

        else:

            temp.setNext(current)

            previous.setNext(temp)

    def isEmpty(self):

        return self.head == None

    def size(self):

        current = self.head

        count = 0

        while current != None:

            count = count + 1

            current = current.getNext()

        return count

     

    def remove(self,item):

        if self.size() != 0:

          current = self.head

          previous = None

          found = False

          while not found and current != None:

              if current.getData() == item:

                  found = True

                  print('Data %s telah dihapus'%item)

              else:

                  previous = current

                  current = current.getNext()

     

          if previous == None:

              self.head = current.getNext()

          else:

              if current != None:

                  previous.setNext(current.getNext())

          if current is None:

            print('Data %s yang dihapus tidak ada di List'%item)

        else:

          print('List sudah Kosong')

     

    def show(self):

        current = self.head

        print('Head',end="->"),

        while current != None:

            print (current.getData(),end= "-> "),

            current= current.getNext()

        print (None)

mylist = OrderedList()

print('==================Program Linked List (Ordered List)==============')

mylist.add(31)

mylist.add(32)

mylist.add(77)

mylist.add(15)

mylist.add(13)

mylist.show()

print(mylist.remove(31))

mylist.show()

print(mylist.search(30))

mylist.show()

Shell Sort

Shell Sort (Metode Shell) 

Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan. 

Proses pengurutan dengan metode Shell dapat dijelaskan sebagai berikut : 

1.    Menentukan  jarak mula-mula dari data yang akan dibandingkan, yaitu N

2.    Data pertama dibandingkan dengan data dengan jarak N / 2

3.    Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar.

4.    Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2.

5.    Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2).

Langkah berikutnya :

1.    Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4

2.    Data pertama dibandingkan dengan data dengan jarak N / 4

3.     Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar

4.     Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4

5.     Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4)

6.    Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.

Algoritma metode Shell dapat dituliskan sebagai berikut :
1. Jarak = N
2. Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9
3. Jarak = Jarak / 2. Sudah = false
4. Kerjakan baris 4 sampai dengan 8 selama Sudah = false
5. Sudah = true
6. j = 0
7. Selama (j < N – Jarak) kerjakan baris 8 dan 9
8. Jika (Data[j] > Data[j + Jarak] maka tukar Data[j],
   Data[j + Jarak].
   Sudah = true
9. j = j + 1

Kode Programnya :

Merged Sort

Merge Sort

Merge Sort atau Urut gabung merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk pengurutan data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar dengan prinsip divide and conquer.

Cara kerja algoritme merge sort :

1.    membagi  larik data yang diberikan menjadi dua bagian yang lebih kecil.

2.    Larik yang baru tersebut kemudian akan diurutkan secara terpisah

3.    Setelah kedua buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik sebelumnya. 

Contoh penerapan atas sebuah larik sebagai data sumber yang akan diurutkan {3, 9, 4, 1, 5, 2} adalah sebagai berikut:

• Larik tersebut dibagi menjadi dua bagian, {3, 9, 4} dan {1, 5, 2}
• Kedua larik kemudian diurutkan secara terpisah sehingga menjadi {3, 4, 9} dan {1, 2, 5}
• Sebuah larik baru dibentuk yang sebagai penggabungan dari kedua larik tersebut {1}, sementara nilai-nilai dalam masing larik {3, 4, 9} dan {2, 5} (nilai 1 dalam elemen larik ke dua telah dipindahkan ke larik baru)
• langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam larik baru yang dibuat sebelumnya.
• {1, 2} <-> {3, 4, 9} dan {5}
• {1, 2, 3} <-> {4, 9} dan {5}
• {1, 2, 3, 4} <-> {9} dan {5}
• {1, 2, 3, 4, 5} <-> {9} dan {null}
• {1, 2, 3, 4, 5, 9} <-> {null} dan {null}

Kode Program Merge Sort:
# Functiont to sort data in merge sort algorithm
def mergeSort(data):
   
    if len(data) > 1:
        # Devided the array in two part
        mid = len(data)//2
        leftHalf = data[:mid]
        rightHalf = data[mid:]
       
        # Recursively call the same function
        mergeSort(leftHalf)
        mergeSort(rightHalf)

        i=0
        j=0
        k=0
       
        while i < len(leftHalf) and j < len(rightHalf):
            if leftHalf[i] < rightHalf[j]:
                data[k] = leftHalf[i]
                i=i+1
            else:
                data[k] = rightHalf[j]
                j=j+1
            k=k+1

        while i < len(leftHalf):
            data[k] = leftHalf[i]
            i=i+1
            k=k+1

        while j < len(rightHalf):
            data[k] = rightHalf[j]
            j=j+1
            k=k+1

numList = [5,8,1,6,3,7,2,4,9]
print('Before sort:')
print(numList)
# Calling 'mergeSort' function by passing number array
mergeSort(numList)
print('After sort:')
print(numList)

Dequeue

DeQueue

DeQueue, dikenal juga sebagai antrian berujung dua (double-ended), adalah suatu koleksi item terurut serupa dengan queue. Perbedaannya? Sifat tidak terikat untuk penambahan dan penghapusan item-item dari antrian. Item baru dapat ditambahkan ke depan atau belakang. Karena itu, item yang ada dapat dihapuskan dari salah satu ujung. Struktur linier hibrida ini menyediakan semua kapabilutas stack dan antrian dalam satu struktur data.

Berikut ini adalah beberapa operasi yang dapat diberlakukan terhadap Deque :

1. deque(), membuat suatu deque baru yang kosong. Tidak perlu parameter dan
    mengembalikan suatu deque kosong.
2. addFront(item), menambahkan suatu item baru ke depan dari deque. Perlu item dan tidak
    mengembalikan apapun.
3. addRear(item), menambahkan suatu item baru ke ekor dari deque. Perlu item dan tidak
    mengembalikan sesuatu.
4. removeFront(), menghapus item depan dari deque. Tidak perlu parameter dan
    mengembalikan item. Deque termodifikasi.
5. removeRear(), menghapus item ujung (ekor) dari deque. Tidak perlu parameter dan
    mengembalikan item. Deque berubah.
6. isEmpty(), menguji apakah deque dalam kondisi kosong. Tidak perlu parameter dan
    mengembalikan suatu nilai boolean.
7. size(), mengembalikan jumlah item dalam deque. Tidak perlu parameter dan
    mengembalikan suatu integer.

Kode Program:

class deQueue:

    def __init__(self):

        self.items = []

    def isEmpty(self):

        return self.items == []

    def addrear(self, item):

        self.items.insert(0,item)

    def removefront(self):

        return self.items.pop()

 

     def addfront(self,item)

  self.item.append()

     def removerear(self)

  return self.items.pop(0,item)

   

    def size(self):

        return len(self.items)

q=deQueue()

q.enqueue(4)

q.enqueue('dog')

q.enqueue(True)

print(q.size())

print(q.dequeue())