Я пытаюсь найти эффективное решение для моей домашней работы. Bubble Sort или Insertion Sort?

Question

Привет всем, у меня есть вопрос. Это моя задача, которая ниже:

Пусть A [] - массив натуральных чисел длины N, который частично отсортирован, т. Е. Существует такой индекс i (0 На этот вопрос какой подход лучше? Пузырьковая сортировка или вставка сортировки? Или есть более эффективное решение? Я предпочел сортировку пузырьков для этой задачи, но я открыт для других мнений

static void bubbleSort(int arr[], int n) 
{ 
    int i, j, temp; 
    boolean swapped; 
    for (i = 0; i < n - 1; i++)  
    { 
        swapped = false; 
        for (j = 0; j < n - i - 1; j++)
        { 
            if (arr[j] > arr[j + 1])  
            { 
                // swap arr[j] and arr[j+1] 
                temp = arr[j]; 
                arr[j] = arr[j + 1]; 
                arr[j + 1] = temp; 
                swapped = true; 
            } 
        } 


        if (swapped == false) 
            break; 
    } 
} 

static void printArray(int arr[], int size) 
{ 
    int i; 
    for (i = 0; i < size; i++) 
        System.out.print(arr[i] + " "); 
    System.out.println(); 
}


 public static void main(String args[]) 
{ 
    int arr[] = { 1, 8, 45, 12, 22, 11, 90 }; 
    int n = arr.length; 
    bubbleSort(arr, n); 
    System.out.println("Sorted array: "); 
    printArray(arr, n); 
} 

}

Answer 1

Сложность алгоритма сортировки пузырьков O (n ^ 2). Даже при использовании if (swapped == false) break; это не поможет уменьшить сложность (попробуйте {2,3,4,5,1}, вы узнаете).

Поскольку существует такой индекс i(0 < i < N-1), что подстрока A[0],...,A[i] сортируется по возрастанию, а также подрешетка A[i+1],...,A[N] сортируется по возрастанию. Эту проблему можно решить в O (n) сложности времени выполнения. Если нам удастся найти индекс i, где A[0:i] and A[i+1:n] are sorted, то эту проблему можно представить как объединение двух отсортированных массивов в один массив, что можно сделать за O (n) раз. Алгоритм приведен ниже:

void sortPartialSortedArray(int arr[], int n) 
{
    int pos = 0; 
    // find the position for which arr[0:pos] and arr[pos+1:n] is sorted
    for(int i=0; i+1<n; i++) {
        if(arr[i]>arr[i+1]) {
            pos = i; 
        }
    }

    int i = pos, j= n-1;

    // sort it from last position
    while(i>=0 && j>=0) {
        if(arr[i] > arr[j]) {
            swap(arr[i],arr[j]);
        }
        j--;
        if(i==j) {
            i--;
        }
    }
}