Tez No	İndirme	Tez Künye	Durumu
497569		Development of sorting and searching algorithms / Sıralama ve arama algoritmalarının geliştirilmesi Yazar:ADNAN SAHER MOHAMMED AL-AJEELI Danışman: PROF. DR. FATİH VEHBİ ÇELEBİ Yer Bilgisi: Ankara Yıldırım Beyazıt Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2017 110 s.
Bilgisayarlarda veri hızındaki artış bilgisayarların hızındaki büyümeden çok daha fazladır ve bu da araştırma literatüründeki sıralama ve arama algoritmalarının üzerinde yoğun bir şekilde durulmasına sebep olmaktadır. Bu tezde, yerleştirmeli sıralama 'insertion sort' kavramına dayalı yeni verimli bir sıralama algoritması öneriyoruz. Önerilen algoritma Çift Yönlü Şartlı Yerleştirmeli Sıralama 'Bidirectional Conditional Insertion Sort (BCIS)' olarak adlandırılır. Bu algoritma bir yerinde sıralama algoritmasıdır ve standart yerleştirme sıralaması ile kıyaslandığında fevkalade verimli ortalama durum zaman karmaşıklığına sahiptir. Yeni algoritmamızı QuickSort algoritması ile kıyasladığımızda, BCIS, 1500 ögeye kadar göreceli olarak küçük dizilerde daha hızlı ortalama durum zamanları göstermektedir. Enterpolasyon (ara değerlemesi) ve ikili arama fikrine dayanarak sıralanmış veri setlerini aramak için hibrit bir algoritma sunuyoruz. Sunulan algoritma Hibrit Arama (HA) olarak adlandırılır ve bilinmeyen dağılımlı sıralı veri setleri üzerinde verimli olarak çalışmak üzere tasarlanmıştır. Deneysel sonuçlar önerdiğimiz algoritmanın benzer bir yaklaşım kullanan diğer algoritmalarla kıyaslandığında daha iyi bir performansa sahip olduğunu göstermiştir. Buna ilaveten, bu çalışma ikili aramanın uygulamasında değinilmemiş bir konuyu açıklamakta ve analiz etmektedir. Bu konu algoritmanın doğruluğunu etkilemese de, performansını azaltmaktadır. Ancak, bu çalışma ikili aramanın karşılaştırma sayısı açısından davranışını açıklamak için kesin bir analitik yaklaşım sunar. Bu metodun yardımıyla, zayıf uygulamanın karmaşıklığı kanıtlanır. Deneysel sonuçlar geniş büyüklükte arama anahtarı kullanıldığında zayıf uygulamanın doğru uygulamadan daha yavaş olduğunu göstermiştir. Bu uygulamanın diğer algoritmalarda mevcut olup olmadığı da ayrıca araştırılmıştır. Son olarak, iki adet verimli arama algoritması sunuyoruz. İlki 'üçlü aramanın gelişmiş bir uygulamasıdır, ikincisi ise Binary-Quaternary search (BQ Arama) 'İkili-Dörtlü Arama' olarak adlandırılan yeni bir algoritmadır. BQ arama yeni verimli bir böl ve yönet tekniği kullanmaktadır. Önerilen her iki algoritma da teorik ve deneysel olarak ikili aramalar ile kıyaslandığında daha iyi performans göstermektedir. Her ne kadar, önerilen BQ arama gelişmiş üçlü aramadan çok az daha yüksek ortalama karşılaştırma sayısı gösterse de, deneysel olarak BQ araması bazı koşullar altında gelişmiş üçlü aramalar ile kıyaslandığında daha iyi performans göstermektedir.
The increase in the rate of data is much higher than the growth in the speed of computers, which results in a heavy emphasis on sort and search algorithms in the research literature. In this thesis, we propose a new efficient sorting algorithm based on the insertion sort concept. The proposed algorithm is called Bidirectional Conditional Insertion Sort (BCIS). It is an in-place sorting algorithm, and it has a remarkably efficient average case time complexity when compared with a standard insertion sort. By comparing our new algorithm with the QuickSort algorithm, BCIS shows faster average case times for relatively small arrays of up to 1500 elements. Furthermore, BCIS was observed to be faster than QuickSort within the high rate of duplicated elements even for large arrays. We present a hybrid algorithm to search ordered datasets based on the idea of interpolation and binary search. The presented algorithm is called Hybrid Search (HS), which is designed to work efficiently on unknown distributed ordered datasets. Experimental results showed that our proposed algorithm has better performance when compared with other algorithms that use a similar approach. Additionally, this study describes and analyses an unaddressed issue in the implementation of the binary search. In spite of this issue not affecting the correctness of the algorithm, it decreases its performance. However, the study presents a precise analytical approach to describe the behavior of the binary search in terms of comparisons number. With the help of this method, the complexity of the weak implementation is proved. Experimental results show that the weak implementation is slower than the correct implementation when a large sized search key is used. The presence of this implementation issue within other algorithms is also investigated. Finally, we present two efficient search algorithms, the first of which is an improved implementation of the ternary search, and the second a new algorithm called Binary-Quaternary search (BQ search). BQ search uses a new efficient divide-and-conquer technique. Both proposed algorithms, theoretically and experimentally, show better performance when compared with binary searches. Although the proposed BQ search displays a slightly higher average comparisons number than the improved ternary search, experimentally the BQ search shows better performance compared with improved ternary searches under some conditions.