Bu proje, c dilinde olup sınırlı sayıdaki talimatlar ile beraber en az hamle sayısı olacak şekilde sıralama yapılmasını sağlayacaktır.
| Talimatlar | Açıklama |
|---|---|
| sa | swap a -> a yığınındaki ilk iki elemanının yeri değişir. |
| sb | swap b -> b yığınındaki ilk iki elemanının yeri değişir. |
| ss | swap a ve swap b -> sa ve sb talimatları aynı anda uygulanır. |
| pa | push a -> b yığınının en üstteki ilk elemanını a yığının en üstüne yerleştirir. |
| pb | push b -> a yığınının en üstteki ilk elemanını b yığının en üstüne yerleştirir. |
| ra | rotate a -> a yığınındaki ilk eleman yığının en sonuna atılır. |
| rb | rotate b -> b yığınındaki ilk eleman yığının en sonuna atılır. |
| rr | ra ve rb -> ra ve rb talimatları aynı anda uygulanır. |
| rra | reverse rotate a -> a yığınındaki son eleman yığının ilk elemanının yerine geçer. Ve artık ilk eleman haline gelir. |
| rrb | reverse rotate b -> b yığınındaki son eleman yığının ilk elemanının yerine geçer. Ve artık ilk eleman haline gelir. |
| rrr | rra ve rrb -> rra ve rrb talimatları aynı anda uygulanır. |
✺ İstenilen algoritma seçilebilecektir. Önemli olan en az hamle için de sıralama yapılmasıdır.
✺ a ve b isimli 2 yığın olacaktır.
✺ Başlangıç da a yığını rastgele sayıda birbirinin kopyası olmayan negative ya da pozitif sayıdan oluşmaktadır. B yığını boştur.
✺ Amacımız yığında küçükten büyüğe artan şekilde sıralama yapmaktır. Ve yığını mümkün olan en az sayıda hamleyle sıralamaktır.
✺ Hata alma durumlarında yani aynı sayı gelme, int max değerini aşımı ve sayıdan farklı bir durum oluştuğunda ekrana Error mesajı bastırılmalıdır.
✺ Bir checker programı yapılacaktır.
✺ Checker çıktıdaki ’\n’ i takip edip satır satır okuyarak talimatların doğru olup olmadığına bakar.
✺ Tüm talimatlar okunup kıyaslama yapıldıktan sonra, Ctrl + D ye basıp, eğer talimatlar doğru ise OK, yanlış ise KO mesajı bastırmalıdır.
✺ Hata alma durumlarında: yani aynı sayı gelme, int max değerini aşımı ve sayıdan farklı bir durum oluştuğunda ekrana Error mesajı bastırılmalıdır.
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quicksort
- Counting Sort
- Radix Sort
- Bucket Sort
- Heap Sort
- Shell Sort
-
Bubble Sort : Bu algoritmada, soldan ilerleyin ve bitişik elemanları karşılaştırın; daha yüksek olan sağ tarafa yerleştirilir. Bu şekilde ilk önce en büyük eleman en sağdaki uca taşınır. Daha sonra bu işleme ikinci en büyük olanı bulmak ve yerleştirmek için devam edilir ve veriler sıralanana kadar bu şekilde devam eder.
-
Selection Sort : Listenin sıralanmamış kısmından en küçük (veya en büyük) öğeyi tekrar tekrar seçer ve onu sıralanmamış bölümün ilk öğesiyle değiştirir. Bu işlem, listenin tamamı sıralanıncaya kadar kalan sıralanmamış kısım için tekrarlanır.
-
Insertion Sort : Elinizdeki oyun kartlarını sıralama şeklinize benzer şekilde çalışan basit bir sıralama algoritmasıdır. Dizi neredeyse sıralanmış ve sıralanmamış bir parçaya bölünmüştür. Sıralanmamış kısımdan değerler alınır ve sıralanmış kısımda doğru konuma yerleştirilir.
-
Merge Sort : Bir diziyi daha küçük alt dizilere bölerek, her bir alt diziyi sıralayarak ve ardından sıralanan alt dizileri son sıralanmış diziyi oluşturmak için yeniden birleştirerek çalışan bir sıralama algoritması olarak tanımlanır.
-
Counting Sort : Sınırlı sayıda giriş değeri olduğunda iyi çalışan, karşılaştırmaya dayalı olmayan bir sıralama algoritmasıdır. Girdi değerleri aralığı, sıralanacak öğelerin sayısıyla karşılaştırıldığında küçük olduğunda özellikle verimlidir. Sayarak Sıralamanın ardındaki temel fikir, giriş dizisindeki her bir farklı öğenin sıklığını saymak ve bu bilgiyi, öğeleri doğru sıralanmış konumlarına yerleştirmek için kullanmaktır.
-
Radix Sort : Öğeleri basamak basamak işleyerek sıralayan doğrusal bir sıralama algoritmasıdır. Sabit boyutlu tuşlara sahip tamsayılar veya dizeler için etkili bir sıralama algoritmasıdır.
-
Bucket Sort : Öğeleri çeşitli gruplara veya kovalara bölmeyi içeren bir sıralama tekniğidir. Bu kovalar elemanların eşit şekilde dağıtılmasıyla oluşturulur. Öğeler gruplara bölündükten sonra başka herhangi bir sıralama algoritması kullanılarak sıralanabilirler. Son olarak, sıralanan öğeler düzenli bir şekilde bir araya getirilir.
-
Heap Sort : İkili Yığın veri yapısına dayalı, karşılaştırmaya dayalı bir sıralama tekniğidir . Bu , ilk olarak minimum elemanı bulduğumuz ve minimum elemanı başlangıca yerleştirdiğimiz seçim sıralamasına benzer . Geriye kalan elemanlar için de aynı işlemi tekrarlayın.
-
Shell Sort : Kabuk sıralaması esas olarak Ekleme Sıralaması'nın bir çeşididir . Eklemeli sıralamada elemanları yalnızca bir konum ileriye taşırız. Bir öğenin çok ileriye taşınması gerektiğinde birçok hareket söz konusu olur. ShellSort'un fikri uzaktaki öğelerin alışverişine izin vermektir. Kabuk sıralamasında, diziyi büyük bir h değeri için h sıralamasına göre yaparız. h'nin değerini 1 olana kadar düşürmeye devam ediyoruz. Her h'inci elemanın tüm alt listeleri sıralanıyorsa, bir dizinin h-sıralı olduğu söylenir.
-
Quicksort : bir öğeyi pivot olarak seçen ve pivotu sıralanan dizide doğru konuma yerleştirerek verilen diziyi seçilen pivot etrafında bölen , Böl ve Fethet algoritmasını temel alan bir sıralama algoritmasıdır .
Algoritma çeşitlerinden ben quicksort algoritmasını seçtim.
Algoritma adımları şu şekilde özetlenebilir:
1- Diziden herhangi bir elemanı pivot(kilit) eleman olarak seçer. 2- Diziyi, pivot elemandan küçük olan bütün elemanlar pivot elemanın önüne, pivot elemandan büyük olan bütün elemanlar pivot elemanın arkasına gelecek biçimde düzenler. 3- Pivot elemana eşit olan sayılar sıralamanın küçükten büyüğe ya da büyükten küçüğe olmasına bağlı olarak pivot elemanın her iki tarafına da geçebilir. 4- Quicksort algoritması özyineli(recursive) çağrılarak, oluşan küçük diziler tekrar sıralanır. 5- Algoritma eleman sayısı sıfır olan bir alt diziye ulaşana kadar bu işlem devam eder. 6- Eleman sayısı sıfır olan bir alt diziye ulaşıldığında algoritma bu dizinin sıralanmış olduğunu varsayar ve sıralama işlemi tamamlanmış olur.
Pivot seçimi : Pivot seçmenin 4 yaygın yolu vardır. Aşağıdaki yöntemlerden herhangi biri kullanılabilir:
1- İlk öğeyi seç
2- Son öğeyi seç
3- Rastgele bir öğe seç
4- Ortanca elemanı seç
Bu proje de biz ortanca elemanı pivot olarak seçtik. Sebebi daha az hamlede sıralamayı yapmak istediğimiz için.
- Buradaki sıralama yaparken a yığınında küçükten büyüğe, b yığınında büyükten küçüğe bir sıralama durumu olmaktadır. İlk durumda b boştur.
- A yığınındaki diziden pivot eleman seçilir. Bu pivot ortanca eleman olacaktır.
- Bunu küçük bir bubble sort yapıp, geçici bir değişken de tutup buldum.
- Şuan a yığınımdaki rastgele, sıralanmamış olan sayılarımdan, a yığınının ilk indisinden başlayarak pivot'a göre kıyaslanıp, pivottan küçük olanları b yığınının en altına gönderilir.
- Bu durum a yığınının boyutunun yarısına kadar devam etmektedir.
- Daha sonra a yığını sıralanana kadar recursive olarak çağırılarak bu işlem devam eder.
- A yığını sıralandığında recursive in kaldığı yerdeki size boyutuyla beraber b yığınına gönderilir.
- B yığınındaki boyut 3 den büyük olursa pivot belirlenir. Olmazsa diğer 3 lü sıralamalar için olan fonksiyonlar çağırılarak işlem yapılır.
- Belirlenen pivot değerinden büyük ve eşit olanlar a yığınının en üstüne gönderilir. Bu işlemde b yığınının boyutunun yarısına kadar devam eder.
- Böylece recursive çağırılıp boyut değişirken, içerdeki boyutun durumuna göre olan fonksiyonları çağırarak a yığınına gönderilip, sıralama yapıp bitirilir.