Verinin tanımı:

Elinizde ikili olarak aralarında bir sıra ilişkisi (<) tarif edilmiş olan, N adet elemandan oluşan [xi | 1 < i < N] bir sıralamalı küme olsun. Ancak bu kümedeki elemanlar rastgele bir sırada bulunuyor olsunlar.

(Örneğin bir defter dolusu karışık sözcük var elinizde, ikili sözcüklerin arasında bir sıra ilişkisi nasıl tanımlanabilir derseniz... diyelim ki 'sıra' deyince alfabetik sıralamadan söz ediyoruz)

Kurallar:

'değiştokuş(i,j)' olarak adlandırılan küme üzerindeki bir işlemle, yalnızca iki elemanın yerlerini değiş tokuş etmenize izin verilmekte. Yani değiştokuş(i,j) işlemi öncesinde belirli biri konumunda bulunana ve belirli bir j konumunda bulunan b ise bu işlemden sonra i konumunda bulunan b ve j konumunda bulunan a olacaktır.

(Yani bu işlemle defterdeki herhangi iki sözcüğün yerlerini değiştokuş edebilirsiniz)

Her hangi bir anda çok az sayıda (en fazlasıyle birkaç) eleman konumunu bir yere kaydetmeniz olanaklıdır.
Bu yolla kaydedilmiş eski bir kayıdın üzerine (eskisini kaybetmek koşulu ile) yeni kayıt yapmak olanaklıdır.

(Diyelim ki elinizde birkaç sözcük konumunu not alabileceğiniz kadarlık bir kağıt parçası ve bir silgi de var)

Amaçlarımız:

*Yalnızca değiştokuş(i,j) ve elemanların sıra ilişkisini (<) kullandığımız öyle bir yöntem bulmak ki sonunda verilen kümedeki elemanlar tümüyle artan sıraya girmiş olsun. Matematiksel deyişle: Bütün i,j ler için xi < xj ise i < j dir.
(Yani, amaç defterdeki bütün sözcükleri, ikili değiştokuşlarla, artan sıraya sokmak)

*Yöntemde kullanılan değiştokuş(i,j) işlemlerinin 'en az' olmasını sağlamak. Bu 'en az' değiştokuş(i,j) sayısını N cinsinden tarif etmek.

Büyük olasılıkla bazı çözümleri kafanızda oluşturdunuz bile. Çözümünüzü irdelediğinizde, verilerin en kötü sıralanışlarında bile yönteminizin en fazlası ile K adet değiştokuş(i,j) işlemi yaparak amacı sağladığını saptadınız. İlk akla gelen çözümler çoğunlukla K=N×(N+1)/2 adet değiştokuş(i,j) gerektirirler. Bu bağımlılığın derecesine 'mertebe' diyoruz. Yani ilk akla gelen (büyük olasılıkla sizin de bulduğunuz) çözümler N2mertebesindedir. Peki en iyi yöntem için bu 'mertebe' nedir diye merak edenler için yanıtı verelim: N×log(N). Verilmiş kurallar çerçevesinde, herhangi bir yöntemin bundan daha iyi bir başarıda olamayacağının tanıtı (ispatı) da Bilgisayar Biliminde mevcut.

Bu arada yeri gelmişken şunu da belirtelim: Bilgisayar Biliminde bu tür yöntemlere 'Algoritma' diyoruz. Merak edenler için: Algoritma sözcüğü, matematiksel olarak bazı cebir işlemlerini bir yöntem olarak betimleyen, 9 Asırın başında yaşamış Acem asıllı matematik bilgini Abu Cafer Muhammed İbn-Musa-Al-Khovarizmi'in adından gelmektedir. Al-Khovarizmi Farsça 'Harzemli' demektir.