Ortaokul Bilgisayar Olimpiyatı 2022, 1. Aşama, Soru 20

[18-19 soruları için açıklama]
Çok iyi iki arkadaş olan Beril ile Selim kendi aralarında yeni bir sıralama algoritması geliştirmeye karar veriyorlar. Mevcut algoritmalara çok benzeyen bu algoritmanın ufak değişiklikleri bulunuyor. Belirlenen bir aralık ile tüm dizi en soldan en sağa kadar geziliyor. Eğer sağdaki sayı daha küçükse bu iki sayı yer değiştiriyor. Tüm dizi bu şekilde gezildikten sonra aralık değeri 1.3 ile bölünüp aşağı yuvarlanıyor ve aynı karşılaştırma işlemi en soldan en sağa kadar tekrar yapılıyor.
Örneğin, elimizde en soldaki sayının 0'nci yerde ve en sağdaki sayımızın 7'nci yerde olduğu bir dizi olsun. Eğer başlangıç aralığımız 5 ise, 0. eleman ile 5. eleman karşılaştırılacak ve ihtiyaç varsa bu iki sayı yer değiştirilecektir. Fakat hala 5. elemanın sağında bakılmamış sayılar kalacağı için kaydırma işlemi gerçekleştirilerek 1. eleman ile 6. eleman ve 2. eleman ile 7. eleman karşılaştırılmaları da yapılacaktır. Aralık büyüklüğü 5/1.3=3 (3.8, fakat aşağı yuvarlandığı için 3 oluyor) olacak şekilde güncellenip en soldan en sağa doğru karşılaştırma işlemi tekrar ediliyor. Bu işlemler aralık sayısı 1'in altına inene kadar tekrar ediliyor.

---

Verilen dizi aşağıdaki gibiyse ve başlangıç aralığımız 8 olduğu durumda;

\[ A = [ 24, 5, 12, 22, 14, 13, 1, 11 ] \]

Kaç farklı aralık kontrolü yapıldığı ve bu kontroller esnasında yapılan karşılaştırmalar sonucunda kaç adet değişiklik yapıldığı bilgisini aşağıdaki seçeneklerden hangisi vermektedir?

Şıklar:
A) 3 aralık – 4 değişiklik 
B) 5 aralık – 5 değişiklik 
C) 3 aralık – 6 değişiklik 
D) 5 aralık – 6 değişiklik 
E) 3 aralık – 5 değişiklik

Cevap: B 5 aralık – 5 değişiklik

Çözüm:
Aralık 8 için 0 karşılaştırma, aralık 6(8/1.3) için 2, aralık 4(6/1.3) için 4, aralık 3(4/1.3) için 5, aralık 2(3/1.3) için 6 ve aralık 1(2/1.3) için 7 karşılaştırma işlemi gerçekleştirilecektir. Toplamı 24 olmaktadır.
Tüm değişiklik tablosu aşağıdaki gibi olacaktır:
<table><tr><td>Aralık</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="2">6</td><td>24</td><td>5</td><td>12</td><td>22</td><td>14</td><td>13</td><td>11</td></tr><tr><td>1</td><td>5</td><td>12</td><td>22</td><td>14</td><td>13</td><td>11</td><td>değiştirme</td></tr><tr><td rowspan="4">4</td><td>1</td><td>5</td><td>12</td><td>22</td><td>14</td><td>13</td><td>24</td><td>11</td></tr><tr><td>1</td><td>5</td><td>12</td><td>22</td><td>13</td><td>24</td><td>11</td><td></td></tr><tr><td>1</td><td>5</td><td>12</td><td>22</td><td>14</td><td>24</td><td>11</td><td>değiştirme</td></tr><tr><td>1</td><td>5</td><td>12</td><td>22</td><td>14</td><td>23</td><td>11</td><td></td></tr><tr><td rowspan="5">3</td><td>1</td><td>5</td><td>12</td><td>11</td><td>14</td><td>13</td><td>24</td><td>22</td></tr><tr><td>1</td><td>5</td><td>12</td><td>11</td><td>14</td><td>13</td><td>22</td><td></td></tr><tr><td>1</td><td>5</td><td>12</td><td>11</td><td>14</td><td>24</td><td>22</td><td></td></tr><tr><td>1</td><td>5</td><td>12</td><td>11<td>14</td><td>13</td><td>24</td><td>22</td></td></tr><tr><td>1</td><td>5</td><td>12</td><td>11</td><td>14</td><td>23</td><td>22</td><td></td></tr><tr><td rowspan="6">2</td><td>1</td><td>5</td><td>12</td><td>11</td><td>14</td><td>13</td></tr><tr><td>1</td><td>5</td><td>12</td><td>11</td><td>14</td><td>14</td><td>22</td><td></td></tr><tr><td>1</td><td>5</td><td>12</td><td>11<br/>14</td><td>14</td><td>13</td><td>24<br/>22</td><td></td></tr><tr><td>1</td><td>5</td><td>12</td><td>11</td><td>13</td><td>24</td><td>22</td><td></td></tr><tr><td>1</td><td>5</td><td>12<br/>11</td><td>14</td><td>13</td><td>24<br/>22</td><td>22</td><td></td></tr><tr><td>1</td><td>5</td><td>12</td><td>11 <br/> 14</td><td>13</td><td>24</td><td>22</td><td></td></tr><tr><td rowspan="7">1</td><td>1</td><td>5</td><td>12</td><td>11</td><td>14</td><td>13</td><td rowspan="7">değiştirme</td></tr><tr><td>1</td><td>5</td><td>12</td><td>11</td><td>14</td><td>22</td><td>22</td></tr><tr><td>1</td><td>5</td><td>12</td><td>11</td><td>13</td><td>22</td><td>22</td></tr><tr><td>1</td><td>5</td><td>12</td><td>12</td><td>14</td><td>23</td><td>22</td></tr><tr><td>1</td><td>5</td><td>12</td><td>12</td><td>13</td><td>24</td><td>22</td></tr><tr><td>1</td><td>5</td><td>11</td><td>12</td><td>14</td><td>23</td><td>22</td></tr><tr><td>1</td><td></td><td>5</td><td>11</td><td>12</td><td>13</td><td>24</td><td>22</td></tr><tr><td></td><td>1</td><td>5</td><td>11</td><td>12</td><td>13</td><td>24</td><td>22</td><td>değiştirme</td></tr><tr><td></td><td>1</td><td>5</td><td>11</td><td>12</td><td>13<br/>14</td><td>24</td><td>22</td><td>değiştirme</td></tr><tr><td></td><td>1<td>5</td><td>11</td><td>12</td><td>13</td><td>24</td><td>22</td><td>son durum</td></td></tr></table>
Açık mavi alanlar karşılaştırma yapılan değerleri gösteriyor. Toplamda 5 değiştirme işlemi yapılacaktır. Aralık büyüklüğü de 6, 4, 3, 2, 1 olacak şekilde 5 farklı döngüde ele alınmıştır.