3-Laboratoriya ishi

Shell saralash usuli.

Qisqichbaqasimon saralash Donald L. Shell tomonidan ixtiro qilingan. Uning o'ziga xosligi shundaki, u butun ro'yxatni aralash sub-ro'yxatlar to'plami sifatida ko'rib chiqadi. Birinchi bosqichda ushbu pastki ro'yxatlar shunchaki elementlarning juftlari. Ikkinchi bosqichda har bir guruhda to'rtta element mavjud. Jarayon takrorlanganda, har bir kichik ro'yxatdagi elementlar soni ko'payadi va pastki ro'yxatlar soni mos ravishda kamayadi.

Shaklda 3.1 ro'yxat 16 ta elementni saralashda ishlatilishi mumkin bo'lgan ichki ro'yxatni ko'rsatadi.

Shaklda 3.1 (a) sakkizta pastki ro'yxatni ko'rsatadi, ularning har ikkitasida ikkita element mavjud bo'lib, unda birinchi pastki ro'yxat birinchi va to'qqizinchi elementlarni, ikkinchi pastki ro'yxat ikkinchi va o'ninchi elementlarni o'z ichiga oladi va hokazo.

Shaklda 3.1 (b) biz allaqachon har birida to'rtta elementning to'rtta pastki ro'yxatini ko'rmoqdamiz. Bu safar birinchi pastki ro'yxat birinchi, beshinchi, to'qqizinchi va o'n uchinchi elementlarni o'z ichiga oladi. Ikkinchi pastki ro'yxat ikkinchi, oltinchi, o'ninchi va o'n to'rtinchi elementlardan iborat. Shaklda

3.1 (c) mos ravishda juft va juft raqamlardan iborat ikkita ichki ro'yxatni ko'rsatadi. Shaklda 3.1 (d), biz yana bitta ro'yxatga qaytamiz.

Dastur kodi :

public static void sort (int[] arr)

{

for (int inc = arr.length / 2; inc >= 1; inc = inc / 2)

for (int step = 0; step < inc; step++)

insertionSort (arr, step, inc);

System.out.println(Arrays.toString(arr));

}
private static void insertionSort (int[] arr, int start, int inc)

{

int tmp;

for (int i = start; i < arr.length - 1; i += inc)

for (int j = Math.min(i+inc, arr.length-1); j-inc >= 0; j = j-inc)

if (arr[j - inc] > arr[j])

{

tmp = arr[j];

arr[j] = arr[j-inc];

arr[j-inc] = tmp;

}

else break;

}