Sortowanie przez wstawianie

Algorytmy: sortowanie i wyszukiwanie - Podstawy Javy (Java)

Zasada działania sortowania przez wstawianie: Tablica jest podzielona na część posortowaną i nieposortowaną W każdym kroku bierzemy pierwszy element z części nieposortowanej Wstawiamy go w odpowiednie miejsce w części posortowanej Przesuwamy pozostałe elementy, aby zrobić miejsce Złożoność algorytmu: Czasowa: O(n²) w przypadku średnim i najgorszym Czasowa: O(n) w przypadku najlepszym (prawie posortowana tablica) Pamięciowa: O(1) - sortowanie w miejscu Porównanie z sortowaniem bąbelkowym: Insertion Sort: Lepszy dla małych tablic Wydajniejszy dla prawie posortowanych danych Mniej operacji zamiany niż w Bubble Sort Bubble Sort: Prostszy w implementacji Zawsze wykonuje pełne przejścia Mniej efektywny dla większości przypadków Przypadki użycia: Małe zbiory danych (do 50 elementów) Prawie posortowane dane Sortowanie w czasie rzeczywistym (gdy elementy przychodzą pojedynczo) Jako część bardziej złożonych algorytmów sortowania

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    // Przykładowa tablica do sortowania
    int[] array = {64, 34, 25, 12, 22, 11, 90};
    
    System.out.println("Tablica przed sortowaniem:");
    System.out.println(Arrays.toString(array));

    // Wywołanie sortowania przez wstawianie
    insertionSort(array);

    System.out.println("\nTablica po sortowaniu:");
    System.out.println(Arrays.toString(array));

    // Demonstracja działania na prawie posortowanej tablicy
    int[] almostSorted = {1, 2, 4, 3, 5, 6, 7, 8};
    System.out.println("\nPrawie posortowana tablica:");
    System.out.println("Przed sortowaniem: " + Arrays.toString(almostSorted));
    insertionSortWithStats(almostSorted);
    System.out.println("Po sortowaniu: " + Arrays.toString(almostSorted));

    // Porównanie z sortowaniem bąbelkowym
    int[] bubbleArray = {64, 34, 25, 12, 22, 11, 90};
    int[] insertionArray = Arrays.copyOf(bubbleArray, bubbleArray.length);
    
    System.out.println("\nPorównanie metod sortowania:");
    System.out.println("Sortowanie bąbelkowe:");
    bubbleSortWithStats(bubbleArray);
    System.out.println("\nSortowanie przez wstawianie:");
    insertionSortWithStats(insertionArray);
  }

  // Podstawowa implementacja sortowania przez wstawianie
  public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
      int key = arr[i];
      int j = i - 1;

      while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j = j - 1;
      }
      arr[j + 1] = key;
      
      // Wyświetlenie stanu tablicy po każdym wstawieniu
      System.out.println("Po wstawieniu " + key + ": " + Arrays.toString(arr));
    }
  }

  // Wersja ze zliczaniem operacji
  public static void insertionSortWithStats(int[] arr) {
    int comparisons = 0;
    int shifts = 0;

    for (int i = 1; i < arr.length; i++) {
      int key = arr[i];
      int j = i - 1;

      while (j >= 0 && arr[j] > key) {
        comparisons++;
        arr[j + 1] = arr[j];
        shifts++;
        j = j - 1;
      }
      arr[j + 1] = key;
      shifts++; // wstawienie klucza
    }

    System.out.println("Liczba porównań: " + comparisons);
    System.out.println("Liczba przesunięć: " + shifts);
  }

  // Implementacja sortowania bąbelkowego do porównania
  public static void bubbleSortWithStats(int[] arr) {
    int comparisons = 0;
    int swaps = 0;
    boolean swapped;

    for (int i = 0; i < arr.length - 1; i++) {
      swapped = false;
      for (int j = 0; j < arr.length - 1 - i; j++) {
        comparisons++;
        if (arr[j] > arr[j + 1]) {
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
          swaps++;
          swapped = true;
        }
      }
      if (!swapped) break;
    }

    System.out.println("Liczba porównań: " + comparisons);
    System.out.println("Liczba zamian: " + swaps);
  }
}

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Podstawy Javy · Zaloguj się, aby zapisać postęp na koncie.