Development of sorting and searching algorithms
Sıralama ve arama algoritmalarının geliştirilmesi
- Tez No: 497569
- Danışmanlar: PROF. DR. FATİH VEHBİ ÇELEBİ
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Ankara Yıldırım Beyazıt Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 110
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Türkçe yazım denetleyen editör
Turkish spelling checker editor
K.MESUT YARIMBIYIKLI
Yüksek Lisans
Türkçe
1992
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ. DR. TAKUHİ NADİA ERDOĞAN
- Mimari tasarım eğitiminde stüdyo kültürü araştırması: Öğrenen-merkezli ortamın yansımaları
Studio culture in architectural design education: Reflections of learner-centered environment
CEMİLE SANEM ERSİNE MASATLIOĞLU
Doktora
Türkçe
2018
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
DOÇ. DR. NURBİN PAKER KAHVECİOĞLU
- Entity framework'ün farklı veri tabanlarındaki performans analizi
Performance analysis of entity framework in different databases
TAHSİN BALCI
Yüksek Lisans
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKırıkkale ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERMAN YÜKSELTÜRK
- 1923- 1995 yılları arasında Türkiye'deki toplumsal değişim süreçlerinin müzik türlerine etkileri
Başlık çevirisi yok
NURLU ERAL
Doktora
Türkçe
1998
Eğitim ve ÖğretimMarmara ÜniversitesiMüzik Eğitimi Ana Bilim Dalı
DOÇ. DR. HİLAL DİCLE
- Enhanced pneumatic ejection for metal sorting and recycling
Başlık çevirisi yok
MURAT HAN TEZEL
Yüksek Lisans
İngilizce
2022
Katholieke Universiteit Leuven (Catholic University of Leuven)PROF. DR. JEF PEETERS
DR. BART ENGELEN