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