http___programarcadegames.com_index.php_chapter_sorting_lang_tr_2.xml
1.1 2.1 3.1 3.2 3.3 4.1 4.2 4.3 5.1 6.1 7.1 8.1 8.2 8.3 8.4 8.5 9.1 10.1 10.2 10.3 12.1 12.2 13.1 14.1 15.1 15.2 15.3 15.4 16.1 16.2 16.3 16.4 17.1 18.1 18.2 18.3 19.1 20.1 20.2 20.3 20.4 20.5 21.1 21.2 21.3 21.4 22.1 22.2 23.1 23.2 23.3 23.4 23.5 24.1 24.2 24.3 24.4 24.5 25.1 26.1 27.1 28.1 29.1 30.1 31.1 32.1 33.1 33.2 33.3 33.4 33.5 34.1 34.2 35.1 35.2 35.3 35.4 36.1 37.1 37.2 37.3 38.1 38.2 38.3 39.1 40.1 41.1 42.1 43.1 44.1 45.1 46.1 47.1 48.1 49.1 49.2 50.1 51.1 52.1 53.1 54.1 55.1 56.1 57.1 58.1 59.1 60.1
Program Arcade GamesWith Python And Pygame Chapter 17: Sorting Binary searches only work on lists that are in order. So how do programs get a list in order? How does a program sort a list of items when the user clicks a column heading, or otherwise needs something sorted? There are several algorithms that do this. The two easiest algorithms for sorting are the selection sort and the insertion sort. Other sorting algorithms exist as well, such as the shell, merge, heap, and quick sorts. The best way to get an idea on how these sorts work is to watch them. To see common sorting algorithms in action visit this excellent website: http://www.sorting-algorithms.com Each sort has advantages and disadvantages. Some sort a list quickly if the list is almost in order to begin with. Some sort a list quickly if the list is in a completely random order. Other lists sort fast, but take more memory. Understanding how sorts work is important in selecting the proper sort for your program. 17.1 Swapping Values Before learning to sort, we need to learn how to swap values between two variables. This is a common operation in many sorting algorithms. Suppose a program has a list that looks like the following: The developer wants to swap positions 0 and 2, which contain the numbers 15 and 14 respectively. See Figure 17.1. A first attempt at writing this code might look something like this: my_list[0] = my_list[2] my_list[2] = my_list[0] See Figure 17.2 to get an idea on what would happen. This clearly does not work. The first assignment list[0] = list[2] causes the value 15 that exists in position 0 to be overwritten with the 14 in position 2 and irretrievably lost. The next line with list[2] = list[0] just copies the 14 back to cell 2 which already has a 14. To fix this problem, swapping values in an array should be done in three steps. It is necessary to create a temporary variable to hold a value during the swap operation. See Figure 17.3. The code to do the swap looks like the following: temp = my_list[0] my_list[0] = my_list[2] my_list[2] = temp The first line copies the value of position 0 into the temp variable. This allows the code to write over position 0 with the value in position 2 without data being lost. The final line takes the old value of position 0, currently held in the temp variable, and places it in position 2. 17.2 Selection Sort The selection by looking at element 0. Then code next scans the rest of the list from element 1 to n-1 to find the smallest number. The smallest number is swapped into element 0. The code then moves on to element 1, then 2, and so forth. Graphically, the sort looks like Figure 17.4. The code for a selection sort involves two nested loops. The outside loop tracks the current position that the code wants to swap the smallest value into. The inside loop starts at the current location and scans to the right in search of the smallest value. When it finds the smallest value, the swap takes place. def selection_sort(my_list): """ Sort a list using the selection sort """ # Loop through the entire array for cur_pos in range(len(my_list)): # Find the position that has the smallest number # Start with the current position min_pos = cur_pos # Scan left to right (end of the list) for scan_pos in range(cur_pos + 1, len(my_list)): # Is this position smallest? if my_list[scan_pos] < my_list[min_pos]: # It is, mark this position as the smallest min_pos = scan_pos # Swap the two values temp = my_list[min_pos] my_list[min_pos] = my_list[cur_pos] my_list[cur_pos] = temp The outside loop will always run $n$ times. The inside loop will run $n/2$ times. This will be the case regardless if the list is in order or not. The loops' efficiency may be improved by checking if min_pos and cur_pos are equal before line 16. If those variables are equal, there is no need to do the three lines of swap code. In order to test the selection sort code above, the following code may be used. The first function will print out the list. The next code will create a list of random numbers, print it, sort it, and then print it again. On line 3 the print statement right-aligns the numbers to make the column of numbers easier to read. Formatting print statements will be covered in Chapter 20. # Before this code, paste the selection sort and import random def print_list(my_list): for item in my_list: print("{:3}".format(item), end="") print() # Create a list of random numbers my_list = [] for i in range(10): my_list.append(random.randrange(100)) # Try out the sort print_list(my_list) selection_sort(my_list) print_list(my_list) See an animation of the selection sort at: http://www.sorting-algorithms.com/selection-sort For a truly unique visualization of the selection sort, search YouTube for “selection sort dance” or use this link: http://youtu.be/Ns4TPTC8whw You can trace through the code using http://pythontutor.com. 17.3 Insertion Sort The insertion sort is similar to the selection sort in how the outer loop works. The insertion sort starts at the left side of the array and works to the right side. The difference is that the insertion sort does not select the smallest element and put it into place; the insertion sort selects the next element to the right of what was already sorted. Then it slides up each larger element until it gets to the correct location to insert. Graphically, it looks like Figure 17.5. The insertion sort breaks the list into two sections, the “sorted” half and the “unsorted” half. In each round of the outside loop, the algorithm will grab the next unsorted element and insert it into the list. In the code below, the key_pos marks the boundary between the sorted and unsorted portions of the list. The algorithm scans to the left of key_pos using the variable scan_pos. Note that in the insertion sort, scan_pos goes down to the left, rather than up to the right. Each cell location that is larger than key_value gets moved up (to the right) one location. When the loop finds a location smaller than key_value, it stops and puts key_value to the left of it. The outside loop with an insertion sort will run $n$ times. The inside loop will run an average of $n/2$ times if the loop is randomly shuffled. If the loop is close to a sorted loop already, then the inside loop does not run very much, and the sort time is closer to $n$. def insertion_sort(my_list): """ Sort a list using the insertion sort """ # Start at the second element (pos 1). # Use this element to insert into the # list. for key_pos in range(1, len(my_list)): # Get the value of the element to insert key_value = my_list[key_pos] # Scan from right to the left (start of list) scan_pos = key_pos - 1 # Loop each element, moving them up until # we reach the position the while (scan_pos >= 0) and (my_list[scan_pos] > key_value): my_list[scan_pos + 1] = my_list[scan_pos] scan_pos = scan_pos - 1 # Everything's been moved out of the way, insert # the key into the correct location my_list[scan_pos + 1] = key_value See an animation of the insertion sort at: http://www.sorting-algorithms.com/insertion-sort For another dance interpretation, search YouTube for “insertion sort dance” or use this link: http://youtu.be/ROalU379l3U You can trace through the code using http://pythontutor.com. 17.3.1 Multiple Choice Quiz Click here for a multiple-choice quiz. 17.3.2 Short Answer Worksheet Click here for the chapter worksheet. You are not logged in. Log in here and track your progress. English version by Paul Vincent Craven Spanish version by Antonio Rodríguez Verdugo Russian version by Vladimir Slav Turkish version by Güray Yildirim Portuguese version by Armando Marques Sobrinho and Tati Carvalho Dutch version by Frank Waegeman Hungarian version by Nagy Attila Finnish version by Jouko Järvenpää French version by Franco Rossi Korean version by Kim Zeung-Il Chinese version by Kai Lin
1.1 2.1 3.1 4.1 5.1 6.1 7.1 8.1 9.1 10.1 11.1 12.1 13.1 14.1 15.1 16.1 17.1 19.1 20.1 21.1 22.1 23.1 24.1 25.1 26.1 27.1 28.1 29.1 30.1 31.1 32.1 33.1 34.1 35.1 36.1 37.1 38.1 39.1 40.1 41.1 42.1 43.1 44.1 45.1 46.1 47.1 48.1 49.1 50.1 51.1 52.1 53.1 54.1 55.1 56.1 57.1 58.1 59.1 60.1 62.1 64.1 66.1 67.1 68.1 69.1 70.1 71.1 72.1 73.1 74.1 75.1 76.1 77.1 78.1 79.1 80.1 81.1 82.1 83.1 84.1 85.1
Arcade Türü Oyun Programlamayıve Bilgisayar Bilimleri Öğrenin English Dutch - Nederlands French Hungarian - Magyar Portuguese - Português Russian - Pycckий Spanish - Español Turkish - Türkçe Chapter 18: Sıralama Bölerek arama sadece sıralanmış listelerde çalışmaktadır. Peki programlar listeleri nasıl sıralarlar? Bir program kullanıcı sütun başlığına tıkladığında öğelerin listesini nasıl sıralar ya da bir şeyin sıralanması gerektiğinde ne yapar? Bunu yapmak için birkaç algoritma vardır. Sıralama yapabilmek için en basit iki algoritma ise selection sort ve insertion sort'dır. Diğer sıralama algoritmaları da bulunmaktadır, mesela shell, merge, heap ve quick sıralama algoritmaları. Çok kullanılan sıralama lgoritmalarının uygulamaları için, alttaki siteye göz atın: http://www.sorting-algorithms.com/ Her sıralama avantaj ve dezavantajlara sahiptir. Bazıları başlangıçta liste neredeyse sıralıysa bu tür listeleri oldukça hızlı sıralar. Bazıları liste tamamen rastgele sıralandıysa o tür listeleri hızlı sıralar. Diğer listeler hızlı sıralanır, fakat daha fazla hafıza tüketir. 18.1 Değerleri Takas Etmek Bir dizide iki değeri değiş tokuş etmek çoğu sıralama algoritmasının ortak işlemidir. Örneğin, programın alttaki gibi bir listesinin olduğunu varsayalım: Geliştirici sırayla 15 ve 14 sayılarını içeren 0 ve 2 konumlarının yerlerini değiştirmek istiyor. Bu kodu yazmak için ilk deneme şuna benzer: list[0] = list[2] list[2] = list[0]Grafikte, gerçekleşen şu olacaktır: Açıkça görünüyor ki bu çalışmıyor. İlk list[0] = list[2] ataması 0 konumundaki 15 değerinin üzerine 2 pozisyonundaki 14 değerinin yazılmasına sebep oluyor ve geri alınamaz kayıp ortaya çıkıyor. Alttaki satırda list[2] = list[0] ile 14 sadece değeri zaten 14 olan 2. hücreye geri kopyalanıyor. Bu sorunu çözmek için, bir dizideki değerlerin yerlerinin değiştirilmesi üç aşamada yapılmalıdır. Değiştirme işlemi esnasında değeri tutması için geçici bir değişken oluşturmak gereklidir. Değişimi yapacak kod alttaki gibidir: temp = list[0] list[0] = list[2] list[2] = temp İlk satır 0 konumundaki değeri temp değişkenine kopyalıyor. Bu, kodun 0 konumuna veri kaybedilmeden 2 konumundaki veriyi yazmasına izin veriyor. Son satırda o anda temp değişkeninde tutulan 0 konumunun eski değeri alınıyor ve 2 konumuna yerleştiriliyor. 18.2 Seçmeli Sıralama Seçmeli sıralama listenin başından başlar. Daha sonra kod listenin kalanını tarar ve en küçük sayıyı bulur. En küçük sayı o konumdakiyle yer değiştirir. Daha sonra kod bir sonraki sayıya kayar. Görsel olarak, sıralama alttaki resimdeki gibidir: Seçmeli sıralama için olan kod iki iç içe döngü içerir. Dış döngü kodun en küçük değerle yer değiştireceği konumu tutar. İç döngü geçerli konumdan başlayarak sağa doğru en küçük değeri tarar. En küçük değeri bulduğunda, değiş tokuş işlemi gerçekleşir. # Seçmeli sıralama def selection_sort(list): # Tüm dizi boyunca döngü for curPos in range( len(list) ): # En küçük sayıya sahip konumu bul # Geçerli konumdan başla minPos = curPos # Kalanını tara for scanPos in range(curPos+1, len(list) ): # Bu konum en küçük mü? if list[scanPos] < list[minPos]: # Bu en küçük, bu konumu en küçük olarak işaretle minPos = scanPos # İki değerin yerini değiştir temp = list[minPos] list[minPos] = list[curPos] list[curPos] = temp Dış döngü yer zaman $n$ kez çalışacaktır. İç döngü $n/2$ kez çalışacaktır. Bu listenin sıralı olup olmadığına bakılmaksızın gerçekleşecektir. Döngülerin verimliliği 16. satırda minPos ve curPos'un eşit olup olmadığının kontrolüyle artırılabilir. Bu değerler eşitse, üç satırlık değiştirme kodunun yapılmasına gerek yoktur. Yukarıdaki sıralama kodunu test etmek için alttaki kod kullanılabilir. İlk fonksiyon listeyi ekrana yazdıracaktır. Sontaki kod rastgele sayılardan oluşan bir liste oluşturacak, onu yazdıracak, sıralayacak ve sonra tekrar yazdıracaktır. def print_list(list): for item in list: print( "%3d" % item,end="" ) print() # Rastgele sayılardan oluşan bir liste oluştur list = [] for i in range(10): list.append(random.randrange(100)) # Sıralamayı dene print_list(list) selection_sort(list) print_list(list) 18.3 Eklemeli Sıralama Eklemeli sıralama seçmeli sıralamaya dıştaki döngünün nasıl çalıştığı konusunda benzerdir. Eklemeli sıralama listenin sol tarafından başlar ve sağ tarafı ile çalışır. Fark ise eklemeli sıralama en küçük elemanı seçip onu yerine koymaz; eklemeli sıralama zaten sıralanmış olanın sağındaki bir sonraki elemanı seçer. Daha sonra ekleme yapacağı doğru yeri bulana kadar her daha büyük elemanı ileri kaydırır. Görsel olarak, şuna benzer: Eklemeli sıralama listeyi iki bölüme ayırır; "sıralanmış" yarısı ve "sıralanmamış" yarısı. Dış döngünün her bir devrinde, algoritma bir sonraki sıralanmamış elemanı alır ve onu listede gerekli araya ekler. Alttaki kodta, keyPos listenin sıralanmış ve sıralanmamış kısımları arasındaki sınırı işaretler. Algoritma scanPos değişkenini kullanarak keyPos'un solunu tarar. Eklemeli sıralamada scanPos'un artmak yerine azaldığına dikkat edin. keyValue'den büyük her hücre konumu bit yöne taşınır(sağa doğru). Döngü keyValue'den daha küçük bir konum bulduğunda, durur ve keyValue değerini onun soluna koyar. Bir eklemeli sıralamada dış döngü $n$ kez çalışacaktır. İç döngü eğer döngü rastgele karıştırıldıysa ortalama $n/2$ kez çalışacaktır. Eğer döngü sıralanmış bir döngüye zaten yakın durumdaysa, iç döngü pek fazla çalışmaz ve sıralama zamanı $n$'e daha yakındır. def insertion_sort(list): # İkinci elemandan başla (konum 1). # Bu elemanı kullanarak listeye # ekleme yap. for keyPos in range(1, len(list)): # Eklenecek elemanın değerini al keyValue = list[keyPos] # Sol tarafa doğru tara scanPos = keyPos - 1 # Her elemana döngü kur, konuma # ulaşana kadar onları kaydır while (scanPos >=0) and (list[scanPos] > keyValue): list[scanPos+1] = list[scanPos] scanPos = scanPos - 1 # Her şey yoldan dışarı taşındı, keyValue # değerini doğru konuma ekle list[scanPos+1] = keyValue 18.4 Tekrar Bu sorular çalışma kağıdı olarak da aynı şekilde indirilebilir: [docx] [doc] [pdf] Çalışma kağıdını tamamladıktan sonra, ne kadar iyi yaptığınızı cevap kağıdına bakarak kontrol edebilirsiniz. Cevap anahtarı buradan indirilebilir: [docx] [doc] [pdf] Çalışma kağıdındaki cevapların tam açıklamasını içeren bir video [buradan] görüntülenebilir. - Yatay bir satıra on adet yıldız (*) yazdıran bir "for" döngüsü yazın. - 10x10 yıldız kutusu yazdıran iki iç içe for döngüsü yazın. - 100 sıfırdan bir dizi oluşturan Python kodu yazın. - Bir sınıf ve nesne arasındaki fark nedir? - Fonksiyon ile metot arasındaki fark nedir? - Uğurlu sayınızı yazdıran bir fonksiyon yazın. - Uğurlu sayınızı yazdıran fonksiyonu çağırın. - Üç sayı alan ve ortalamasını döndüren bir fonksiyon yazın. - Programlama sınıfları: - Top isimli bir sınıf için kod yazın. pozisyon ve hız niteliklerini verin. - update() isimli, topun hızına göre konumunu ayarlayacak bir metot oluşturun. - Ball sınıfının bir örneğini oluşturup niteliklerini ayarlayın. - Create a for loop that will call the update() method on ball 10 times, and print the ball's position. Top için update() metodunu 10 kere çağıracak ve topun konumunu ekrana yazdıran bir for döngüsü oluşturun. - 25 ile 40'ın yerlerini değiştiren kod yazın. - 2 ile 25'in yerlerini değiştiren kod yazın. - Alttaki kod neden çalışmaz? - Alttaki sayı listesinin nasıl sıralandığını seçmeli sıralamayı kullanarak gösterin: - Alttaki sayı listesinin nasıl sıralandığını seçmeli sıralamayı kullanarak gösterin: - Alttaki sayı listesinin nasıl sıralandığını eklemeli sıralamayı kullanarak gösterin: - Alttaki sayı listesinin nasıl sıralandığını eklemeli sıralamayı kullanarak gösterin: - Seçmeli sıralamada minPos'un ne yaptığını açıklayın. - Seçmeli sıralamada curPos'un ne yaptığını açıklayın. - Seçmeli sıralamada scanPos'un ne yaptığını açıklayın. - Eklemeli sıralamada keyPos ve keyValue değişkenlerinin ne olduğunu açıklayın. - scanPos'un eklemeli sıralamada olmasını açıklayın. - Sıralamaları iç döngünün ve dış döngünün kaç kez çalıştığını ekrana yazdıracak şekilde değiştirin. 18.4.1 Önceki Bölümler 18.4.2 Sıralama Bölümü You are not logged in. Log in here and track your progress. English version by Paul Vincent Craven Spanish version by Antonio Rodríguez Russian version by Vladimir Slav Turkish version by Güray Yildirim Portuguese version by Armando Marques Sobrinho and Tati Carvalho Dutch version by Frank Waegeman Hungarian version by Nagy Attila French version by Franco Rossi