boubble sorun

Alıştırma 1: Yineleme
Alıştırma 2: Yineleme
H10->H2 çevrimini yapınız
7
1
2
3
1
2
1
2
1
0
Hafta 3: Yineleme Alıştırmaları(1)
E1. (44/174) S değerini yineleme kullanarak
hesap ediniz
–
S = 1 + 2 + 3 + …n
Hafta3: Yineleme Alıştırmaları (2-3)
E3(a). Bir sayıyı tersten yazdıran bir program
yazımız. Örnek: input n=12345. Print out:
54321.
E3(b). Bir sayıyı olduğu gibi yazdıran
programı yineleme ile yeniden yazdırınız.
Örnek: input n=12345. Print out:12345.
Hafta3: Yineleme Alıştırmaları (4)
E4. Bir tamsayının elemanlarını toplayarak
sonucu elde eden programı yineleme mantığı
ile
yazınız.
Örnek:
n=1980
=>
Toplam=1+9+8+0=18.
Hafta3: Yineleme Alıştırmaları(5)
E4. aşağıdaki hesabı yineleme mantığı ile
kodlayınız :
–
S=a[0]+a[1]+…a[n-1]
A: tamsayıların bir dizisi
Hafta3: Yineleme Alıştırmaları (6)
E4. bir dizideki bir elemanı yinelemeli bir
fonksiyon yardımıyla bulma (doğrusal arama
algoritması kullanılacak)
Hafta3: Yineleme Alıştırmaları (7)
Üçgenleri yazdırın
c
a
b
d
Hafta3
Kısım 3: ARAMA TEKNİKLERİ
1. DOĞRUSAL (SIRALI) ARAMA
2. İKİLİ ARAMA
3. ALGORİTMALARIN KARMAŞIKLIĞI
ARAMA TEKNİKLERİ
Bir elemanın listede olup olmadığını bulmak
için yerine getirilir.
2 yöntemi vardır: doğrusal arama ve ikili
arama
Kullanılacak metot veri listesinin nasıl
organize edildiği ile ilgilidir
–
Sırasız liste:
Doğrusal arama: basit, yavaş
–
Sıralı liste:
İkili ve doğrusal arama: karmaşık, daha hızlı
1. DOĞRUSAL (SIRALI) ARAMA
Nasıl?
–
–
–
–
Aranan eleman listedeki elemanlarla sırayla
karşılaştırılır
Bu işlem eleman bulunana kadar veya liste
sonuna varana kadar devam eder.
Eğer eleman bulunursa geriye elemanın sırası
bilgisi döndürülür
Eğer listenin sonuna kadar bir eşleşme olmazsa
arama başarısızlıkla sonuçlanır.
1. DOĞRUSAL (SIRALI) ARAMA
void lsearch(int list[],int n,int element)
{ int i, flag = 0;
for(i=0;i<n;i++)
if( list[i] == element)
{ cout<<“found at position”<<i);
flag =1;
break; }
if( flag == 0)
cout<<“ not found”;
}
flag: what for???
1. DOĞRUSAL (SIRALI) ARAMA
int lsearch(int list[],int n,int element)
{ int i, find= -1;
for(i=0;i<n;i++)
Farklı bir flag kullanımı
if( list[i] == element)
{find =i;
break;}
return find;
}
average time: O(n)
2.
İKİLİ ARAMA
İlk olarak liste sıralanır
Biz aranan elemanı listenin ortasındaki
elemanla karşılaştırırız.
Eğer bir eşleşme bulunursa, arama başarıyla
sonlanır.
Aksi takdirde, biz aranan eleman ile ortadaki
elemanın durumuna göre listenin sağ
tarafında veya sol tarafında aramaya devam
ederiz.
Baba?
Eat?
void bsearch(int list[],int n,int element)
{
int l,u,m, flag = 0;
l = 0; u = n-1;
while(l <= u)
{ m = (l+u)/2;
if( list[m] == element)
{cout<<"found:"<<m;
flag =1;
break;}
else
if(list[m] < element)
l = m+1;
else
u = m-1;
}
if( flag == 0)
cout<<"not found";
}
average time: O(log2n)
İKİLİ ARAMA: Yineleme
int Search (int list[], int key, int left, int right)
{
if (left <= right) {
int middle = (left + right)/2;
if (key == list[middle])
return middle;
else if (key < list[middle])
return Search(list,key,left,middle-1);
else return Search(list,key,middle+1,right);
}
return -1;
}
3. ALGORİTMA KARMAŞIKLIĞI
Bilgisayar biliminde, algoritmaların kalitesini ölçmek
önemlidir, özellikle algoritmaların ihtiyaç duyduğu
kaynaklar bakımından
Kaynaklar: zaman veya bellek alanı
Aynı işi yapan farklı algoritmalar daha az veya daha
fazla zamana, belleğe veya emeğe ihtiyaç
duyabilirler.
Bu analizin güçlü bir matematiksel geri planı vardır.
Bir algoritmanın kalitesini bulma yolu genellikle
Asymptotic Notation veya Big O olarak adlandırılır.
3. ALGORİTMA KARMAŞIKLIĞI
Genellikle
olarak yazılır
Polinom zamanlı algoritmalar,
–
–
–
O(1) --- sabit zamanlı --- problem boyutuna bağlı olarak zaman
değişmez.
O(n) --- doğrusal zamanlı --- problem boyutu büyüdükçe zaman
doğrusal olarak artar.
O(n2) --- ikinci dereceden zaman --- problem boyutunun karesi
hızında problem karmaşıklığı artar. Big O notasyonu kullanılırken
en büyük karmaşıklık problemin karmaşıklığını verir. Örnek; O(3n2
+ 3n + 7) = O(n2)
Alt-doğrusal zamanlı algoritmalar
–
O(logn) – logaritmik zaman
Süper polinomsal zamanlı algoritmalar
–
–
O(n!)
O(2n)
3. ALGORİTMA KARMAŞIKLIĞI
Örnek1: bir algoritmanın karmaşıklığı
void f ( int a[], int n )
{
int i;
cout<< "N = “<< n;
for ( i = 0; i < n; i++ )
cout<<a[i];
printf ( "n" );
}
2 * O(1)? + O(N)
O(N)
?
3. ALGORİTMA KARMAŞIKLIĞI
Örnek2: bir algoritmanın karmaşıklığı
void f ( int a[], int n )
{ int i;
cout<< "N = “<< n; // O(1)
2)
2 * O(1) + O(N)+O(N
?
for ( i = 0; i < n; i++ )
for (int j=0;j<n;j++)
cout<<a[i]<<a[j]; // O(N2)
for ( i = 0; i < n; i++ )
cout<<a[i]; // O(N)
printf ( "n" ); // O(1)
}
O(N2)
?
3. ALGORİTMA KARMAŞIKLIĞI
Doğrusal arama
–
O(n).
İkili arama
–
O(log2 N)
Hafta4: (Kısım4)
20 puanlık test
–
–
Küçük bir program yazın
Bir dizinin eleman sayısını girin
Dizinin elemanlarını girin
Diziyi ekranda gösterin
Bir değer alın. Doğrusal aramayı kullanarak ilk
eşleşmenin pozisyonunu bulun
enterarray,
displayarray,
linearfind
fonksiyonlarını
kullanarak bu işlemi yapın.
Hafta 4: (Kısım 4)
SIRALAMA TEKNİKLERİ
Neden?
–
–
İkili aramayı kullanırız
Bazı işlemleri daha hızlı yapar
SORTING
SIRALAMA TEKNİKLERİ
Verilen n adet elemanın bir kümesi
–
Bir dizi, kelimeler kümesi veya benzeri olabilir
Varsayım elemanlara erişim için bir sıra vardır
Hedef elemanları artan sırada bir sırada düzenleme
–
–
Başlangıç
Sonuç
1 23 2 56 9 8 10 100
1 2 8 9 10 23 56 100
SIRALAMA TEKNİKLERİ
Bubble sort, Insertion sort, Selection sort,
Quick sort, Heap sort, Merge sort, Exchange
sort …
Çalışılacak sıralama teknikleri
–
–
–
–
–
Bubble sort
Insertion sort
Selection sort
Exchange sort
Quick sort
SIRALAMA TEKNİKLERİ
Average
Worst
Bubble sort
O(n2)
Exchange sort
Insertion sort O(n2)
O(n2)
Selection sort O(n2)
O(n2)
Quick sort
O(n2)
O(nlogn)
O(n2)
1.Bubble sort: ana fikir
Listenin elemanlarını komşu elemanların
çiftlerini kullanarak düzenler.
ith ve (i+1)th eleman bir çift oluşturur.
Eğer sıra artan ise, biz listenin elemanlarını
yer değiştiririz.
Bu, geriye kalan n-1 elemanın en büyüğünü
n-1 pozisyonuna getirecektir.
1.Bubble sort: idea
Why it is called Bubble?
3
7
5
2
4
compare 3 and 7 ; 7 is > 3 so advance
3
5
7
2
4
compare 7 and 5, 7 > 5 so swap them
3
5
2
7
4
compare 7 and 2, 7 >4 so swap them
3
5
2
4
7
compare 7 and 4, 7 >4 so swap them
End of pass 1; notice that 7 is in the right place
2.Bubble sort: ana fikir
En basit sıralama algoritması
Ana fikir:
–
–
1.flag = false
2.Diziyi hareket ettir ve elemanları ikili olarak
karşılaştır
1.1 If E1 ≤ E2 - OK
1.2 If E1 > E2 then Switch(E1, E2) and set flag = true
–
3. If flag = true goto 1.
İşlem tamam.
1.Bubble sort: algoritmanın fikri
void bubbleSort (Array S, length n) {
boolean isSorted = false;
while(!isSorted)
{
isSorted = true;
for(i = 0; i<n; i++)
if(S[i] > S[i+1])
{
swap(S[i],S[i+1];)
isSorted = false;
}
}
1.Bubble sort: gerçekleştirim
void bsort(int list[], int n)
{
int count,j;
for(count=0;count<n-1;count++)
for(j=0;j<n-1-count;j++)
if(list[j] > list[j+1])
swap(list[j],list[j+1]);
}
2. Exchange Sorting
Method : veri n-1 kere taranır, her bir
taramada komşu elemanlar karşılaştırılır,
gerekli ise n-1 karşılaştırma yapılır
O(n2)
2. Exchange Sorting
void Exchange_sort(int arr[], int n)
{
int i,j;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(arr[i] > arr[j])
swap(arr[i],arr[j]);
}
2. Exchange Sorting
Notlar:
–
–
–
Her başarılı taramada, bir tane daha az
karşılaştırma yapılır, çünkü son eleman her
tarama sonunda yerini bulur
Eğer bir taramada hiç değişiklik olmazsa işlem
sona erer
Performansını artırmak için bazı çalışmalar
yapılmış olmakla birlikte hala karmaşıklığı O(n2)
dir.