Veri Yapıları - Ders Notu - Süper
Transkript
Veri Yapıları - Ders Notu - Süper
3. Insertion Sort Strateji: koleksiyonu iki listeye böl, tek elemanlı bir liste (sıralı) ve geriye kalan elemanların listesi şeklinde. Her başarılı geçişte sıralı olmayan listeden bir elemanı al ve sırayı bozmayacak şekilde o elemanı sıralı listeye ekle Sırasız listenin sonuna kadar bu işlemi yap. 3. Insertion Sort sorted unsorted 3 7 5 sorted 3 2 Sırasız listeden bir eleman al (7) ve sıralı listeye ekle unsorted 7 5 2 sorted 3 4 5 4 unsorted 7 2 Sırasız listeden bir sonraki elemanı al (5) ve sıralı listeye ekle (sıra bozulmayacak şekilde) 4 Aynı işlemi 2 için yap sorted 2 3 unsorted 5 7 4 Aynı işlemi 4 için yap sorted 2 3 4 unsorted 5 7 3. Insertion Sort void insertionSort(int arr[], int n){ int j, key; for(int i = 1; i < n; i++){ key = arr[i]; j = i - 1; while(j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } 3. Insertion Sort Her bir insertion O(n-1) zamanda meydana gelir, n-1 sayıda da eleman için insertion yapıldığından algoritmanın karmaşıklığı O(n2) dir. 4. Selection Sort Strateji: en yüksek görünen değerler arasında karşılıklı geçiş yapılır, (n-1) elemanın en büyüğü ile dizinin sonundaki eleman yer değiştirilir. Her başarılı geçişte üzerinde işlem yapılacak eleman sayısı 1 azalır. Her geçişte bir eleman yerini bulur. biggest 4. Selection Sort last 3 7 5 2 4 3 4 5 2 7 biggest last 3 4 5 2 7 3 4 2 5 7 biggest last 3 4 2 5 7 3 2 4 5 7 3 2 4 5 7 2 3 4 5 7 4. Selection Sort void selection_sort(int arr[], int n) {int i, j, min; for (i = 0; i < n - 1; i++) { min = i; for (j = i+1; j < n; j++) { if (list[j] < list[min]) min = j; } swap(arr[i],arr[min]); } } 4. Selection Sort Selection sort algoritmasında olası en az yer değiştirme bulunur. Her bir geçişte geriye kalan elemanlar arasında bir karşılaştırma işlemi yapılır. O nedenle karmaşıklığı O(n2) dir. Bu metot O(n2) karmaşıklığındaki algoritmalar içerisinde en iyi performansı veren algoritmadır. 5. Quick Sort Sıralama metotları arasında en hızlı olan metottur. Karmaşıklığı log2n dir. Sıralı veya hemen hemen düzgün sırada verilmiş diziler söz konusu olduğunda problemli çalışır Bu türden problemler için çözüm önerileri getirilmiştir. Onu daha iyi hale getirebilmek için bir iyileştirme vardır. 5. Quick Sort Sıralama algoritmaları “DIVIDE AND CONQUER” (böl ve yönet) paradigmasına dayanır. – – – En sık kullanılan paradigmalardan biridir. Bir problem daha küçük alt problemlere bölünür ve çözümler birleştirilir. Gerçek hayatta sıklıkla kullanılan bir yöntemdir. 5. Quick Sort quick-sort algoritmasını anlamak için, algoritmanın yüksek seviyeli anlatımına göz atmak lazımdır. 1) Divide : eğer, S serisini 2 veya daha fazla elemanı varsa, S içinden bir x elemanı pivot olarak seçilir. Pivot herhangi bir eleman olabilir. Bu işlemin ardından S dizisi aşağıdaki gibi 3 alt diziye ayrılır: L, S’nin x değerinden küçük olan elemanları E, S’nin x’e eşit elemanları G, S’nin x değerinden büyük elemanları 2) Recurse: Yinelemeli olarak L ve G sıralanır 3) Conquer: En sonda, elemanlar yeniden S dizisine sıralı şekilde konulur, ilkinde L’nin elemanları, sonra E’nin en sonunda da G’nin elemanları yerleştirilir. 5. Quick Sort: fikir 1) Select: bir eleman al 2) Divide: elemanları pivot elemanına göre yeniden düzenle 3) Recurse and Conquer: yinelemeli olarak sırala 5. Quick Sort: idea Quick Sort En soldaki eleman pivot olarak alınsın (23). Şimdi, hem sağdan hem soldan elemanlar karşılaştırılarak ortadak elemana kadar gerekli yer değiştirme yapılsın. En son kalan eleman da pivot ile karşılaştırıldıktan sonra uygun yere alınarak divide aşaması bitirilsin. 23 17 5 12 19 24 4 43 34 11 3 33 14 26 8 27 swap 23 17 5 12 19 8 4 43 34 11 3 33 14 26 24 27 3 33 43 26 24 27 34 33 43 26 24 27 swap 23 17 5 12 19 8 4 14 34 11 swap 23 17 5 12 19 8 4 14 3 11 swap Sonunda, pivot ile ortada kalan eleman yer değiştirilir. 11 17 5 12 19 8 4 14 3 23 34 33 43 Not : 23 şu anda olması gereken yerde, solundakilerin hepsi ondan küçük, sağındakilerin hepsi de ondan büyük 26 24 27 Quick Sort Şimdi aynı işlemi sağ taraf için yapalım 11 17 5 12 19 8 4 14 3 8 4 14 3 8 12 14 17 14 17 swap 11 17 5 12 19 swap 11 3 5 4 19 swap 11 3 5 4 8 19 12 swap 8 3 5 4 11 Not: 11 şu anda doğru yerde 19 12 14 17 23 34 33 43 26 24 27 Quick Sort (worst case) Eğer veri zaten sıralı ise ne yapacağız o zaman 3 4 5 8 11 12 14 17 19 23 24 26 27 33 34 43 23 24 26 27 33 34 43 Yer değiştirme işlemi yoktur. 4 5 8 11 12 14 17 19 Parçalar maksimum boyutta ve performans O(n2)’ye kadar düşer. Quick Sort void quickSort(int Arr[], int lower, int upper) { int x = Arr[(lower + upper) / 2]; int i = lower; int j = upper; do{ while(Arr[i] < x) i ++; while (Arr[j] > x) j --; if (i <= j) { swap(Arr[i], Arr[j]); i ++; j --; } }while(i <= j); if (j > lower) quickSort(Arr, lower, j); if (i < upper) quickSort(Arr, i, upper); } Week 5: STACKS ve QUEUES STACKS: kavramı QUEUES : kavramı STACKS,QUEUES : gerçekleştirimi – – Dizi yardımıyla Bağlı liste (Linked List) yardımıyla 1.Stack LIFO (son gelen ilk çıkar) 1.Stack Tepe eleman yönetimi 1.Stack: dizi ile gerçekleştirim #define MAX 10 void main() { int stack[MAX]; int top = -1; push(stack,top, 10 ); pop(stack,top,value); int value; cout<<value; } 1.Stack: dizi ile gerçekleştirim void push(int stack[], int &top, int value) { if(top < MAX ) { top = top + 1; stack[top] = value; } else cout<<"The stack is full"; } 1.Stack: dizi ile gerçekleştirim void pop(int stack[], int &top, int &value) { if(top >= 0 ) { value = stack[top]; top = top - 1; } else cout<<"The stack is empty "; } 2.QUEUE FIFO (ilk gelen ilk çıkar) 2.QUEUE: dizi ile gerçekleştirim Dairesel bir kuyruk 2.QUEUE: dizi ile gerçekleştirim #define MAX 10 void main() { int queue[MAX]; int bottom,top,count=0; bottom=top=-1; enqueue(queue,count,top,100); // kuyruğa at int value; dequeue(queue,count,bottom,top,value); // kuyruktan al } 2.QUEUE: dizi ile gerçekleştirim void enqueue(int queue[],int &count, int &top, int value) { if(count< MAX) { count++; top= (top +1)%MAX; queue[top] = value; } else cout<<"The queue is full"; } 2.QUEUE: dizi ile gerçekleştirim void dequeue(int queue[], int &count,int &bottom,int top, int &value) { if(count==0) { cout<<"The queue is empty"; exit(0); } bottom = (bottom + 1)%MAX; value = queue[bottom]; count--; } 3. Application of stack, queue Stack: Expression evaluation – a*(b–c)/d => abc–*d/ Queue: priority queues Exercise: Implement: 5 sort algorithms Implement stack, queue using array – Menu with 4 choices Add, remove, display, exit