Insertion Sort

Insertion Sort, elementləri tək-tək götürüb sıralanmış hissədə düzgün yerinə yerləşdirən sadə və effektiv bir sıralama alqoritmidir. Bu alqoritm, kart oyunu zamanı əldəki kartları sıralamağa bənzəyir.

Insertion Sort-un Əsas Xüsusiyyətləri

• Adaptiv: Artıq sıralanmış massivlər üçün çox effektivdir
• Stabil: Eyni dəyərə malik elementlərin nisbi sırası qorunur
• İn-place: Əlavə yaddaş tələb etmir
• Online: Məlumatlar gəldikcə sıralaya bilər

Insertion Sort-un İşləmə Prinsipi

1. Başlanğıc: Birinci elementi sıralanmış hesab et
2. Götürmə: Növbəti elementi götür
3. Müqayisə: Sıralanmış hissədə düzgün yeri tap
4. Yerləşdirmə: Elementi düzgün yerinə yerləşdir
5. Təkrar: Bütün elementlər sıralanana qədər təkrarla

Insertion Sort-un Java-da İmplementasiyası

Koda bax

public class InsertionSort {
    
    // Ana sıralama metodu
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        
        // İkinci elementdən başla (birinci element sıralanmış sayılır)
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            
            // key-dan böyük olan elementləri bir mövqe sağa dəyiş
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            
            // key-i düzgün yerinə yerləşdir
            arr[j + 1] = key;
        }
    }
    
    // Rekursiv implementasiya
    public static void recursiveInsertionSort(int[] arr, int n) {
        // Bazis hal
        if (n <= 1) {
            return;
        }
        
        // İlk n-1 elementi sırala
        recursiveInsertionSort(arr, n - 1);
        
        // Son elementi düzgün yerinə yerləşdir
        int last = arr[n - 1];
        int j = n - 2;
        
        while (j >= 0 && arr[j] > last) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = last;
    }
    
    // Test
    public static void main(String[] args) {
        int[] arr1 = {12, 11, 13, 5, 6};
        int[] arr2 = {12, 11, 13, 5, 6};
        
        System.out.println("Original array:");
        printArray(arr1);
        
        // İterativ üsul
        insertionSort(arr1);
        System.out.println("\nSorted array (iterative):");
        printArray(arr1);
        
        // Rekursiv üsul
        recursiveInsertionSort(arr2, arr2.length);
        System.out.println("\nSorted array (recursive):");
        printArray(arr2);
    }
    
    // Massivi çap etmək üçün köməkçi metod
    private static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

Zaman və Yaddaş Mürəkkəbliyi

• Zaman Mürəkkəbliyi:
  • Ən yaxşı hal: O(n) - artıq sıralanmış massiv
  • Orta hal: O(n²)
  • Ən pis hal: O(n²) - tərs sıralanmış massiv
• Yaddaş Mürəkkəbliyi: O(1), in-place alqoritm

Insertion Sort-un Üstünlükləri və Çatışmazlıqları

Üstünlüklər

• Sadə implementasiya və anlama
• Kiçik massivlər üçün çox effektivdir
• Adaptive - artıq sıralanmış məlumatlar üçün O(n) performans
• Stabil sıralama alqoritmidir
• In-place - əlavə yaddaş tələb etmir
• Online - məlumatlar gəldikcə işləyə bilər

Çatışmazlıqlar

• Böyük massivlər üçün O(n²) performans səbəbiylə effektiv deyil
• Bubble sort və selection sort-a nisbətən çox yazma əməliyyatı tələb edir