Girdi sayilari siralama

[sakruh]

Merhaba arkadaslar,

Benim bir odevim var ve sizin onerilerinizi bekliyorum. Soru su :

N tane sayiyi buyukluk-kucukluk iliskisine gore siralayan bir program yazin. Bu islem sirasinda sadece 2 komsu sayi yer degistirebilir. Program N kadar sayiyi minimum olarak kac kez siraladiginin ciktisini vermelidir.

Input : Her test sadece 1 numara iceren "N" ile baslar. Ve alt satir N kadar numara icerir.

Outptu : Her durum icin bir satir cikti verilir.

Ornegin :

Input:
5
1 2 3 4 5
10
8 1 9 52 55 12 -10 1 1 1
2
10 1

Output:
0
24
1

Evet, arkadaslar nereden baslayayim, nasil bir yok izleyeyim; onerilerinizi bekliyorum...

[acehreli]

Adini soylemediklerine gore, bahsettigin siralama algoritmasini da senin olusturmani bekliyorlar. Onun icin ben de soylemiyorum. :) Ama soyle anlatilabilir... Elinde soyle bir dizi olsun:

3 2 5 4 1

1) En bastaki sayiyla basla. (yani 3)

2) Bir sonrakiyle (2) karsilastir

3) Eger sirada bozukluk varsa (var), yani onceki sonrakinden buyukse degis tokus et. Simdi su var:

2 3 5 4 1

4) Simdi bir sonraki cifte bak ve 3'uncu adimi tekrarla. (3 5'ten buyuk olmadigi icin oyle kalsinlar) Sonra 5-4'e gec. Onlari degistirmen gerekiyor:

2 3 4 5 1

Sonra 5-1'e bak:

2 3 4 1 5

En buyuk sayinin en sona otelenmesini saglamis olduk.

5) Simdi 1'inci adima geri dOn ama sondan bir once bitir, cunku en sondaki bakmak gerekmedigini biliyoruz (en buyuk olani en sona otelemistik).

Yani sunlari karsilastiracagiz:

2-3: guzel
3-4: guzel
4-1: degis tokus: 2 3 1 4 5

Simdi de 4'un dogru yerde olmasini sagladik...

Ayni sekilde bastan baslayarak hep sondan bir eksik sayiya bakarsan, once 3, sonra da 2 yerlerine gideceklerdir: 1 2 3 4 5

Simdi bu algoritmayi ic ice dOngUlerle kur. :) Herhalde ic ice iki tane gerekecek, cunku hem 3'uncu adimi tekrarlamak gerekti, hem de sonunda da 1'inci adima dOnmemiz gerekti...

Ali

[golgepapaz]

daha iyi performans icin (belkide extra not :) ) bunun iki yonlu olan varyasyonunu (isim bende vermiyim) deneyebilirsin, yani listeyi bir yukardan asagi , bir asagidan yukari tarayip siralama yaparsan, bu siralamanin performansini iyilestirebilirsin
Ornegin

2 3 4 5 1 klasik algoritmayla yaparsan 1 in en basa gelmesi icin 4 kez taraman gerekiyor, ama tersten baslarsan 1 seferde butun diziyi siralamis olursun.Odevin sartlarini da karsiliyor zaten,gerci hocana aciklaman gerekebilir yanlis calistigini sanmasin diye

[sakruh]

arkadaslar, hepinize tesekkurler. aslinda ben algoritmayi kurmustum; acehreli'nin verdigi ornek cercevesinde. benim sorunum genel olarak algoritmayi koda aktaramamak. daha dogrusu daha karmasik algoritmalari -mesela icice bircik dongu gerektiren, dizi degiskenlerle kontrol edilen donguleri- kodlarken sikinti cekmek. bunda eminim ki kodlamaya yeni baslamanin etkisi de soz konusudur. bu yonde de tavsiyelerinizi bekliyorum... tesekkurler...

[ortug]

sakruh, bu kodlamayı mümkün olduğunca kendin yapmaya çalış. Üzerinde düşündükçe kodlama yeteneklerin gelişecektir, çözdükçe de zevk alacaksın ;)

golgepapaz:
Ben sondan veya baştan başlamanın farkını göremiyorum :s
İnşallah sadece verilen örnek için konuşmuyorsun :iih:

[Euclides]

@ortug:
sondan yada baştan değil, her iki taraftanda.Gene ortalama O(n**2) ama yaklaşık sıralı bir listede O(n)'e yaklaşıyor. (1. algoda her zaman O(n**2))

[golgepapaz]

@ortug:
sondan yada baştan değil, her iki taraftanda.Gene ortalama O(n**2) ama yaklaşık sıralı bir listede O(n)'e yaklaşıyor. (1. algoda her zaman O(n**2))

euclides'in dediginden. google cocktail sort.