Индивидуальная сортировка элементов в массиве

Question

Я слышал о методах сортировки, таких как quicksort, bubblesort, mergesort и многие другие. У меня есть массив как

arr[]={2, 3, 4, 1, 9, 5, 1, 2, 6, 8, 1, 3} 

Использования пузырьковой сортировки я могу получить сортировку сделана как

arr[]={1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 8, 9} 

Но мне нужно, чтобы отсортировать данный массив таким образом

arr[]={1, 2, 3, 4, 5, 6, 8, 9, 1, 1, 2, 3) 

То есть, любые повторные события значений должны быть перенесены в конец массива.

Моя идея - сначала запустить пузырьки массива, а затем использовать этот отсортированный массив, пересекая массив, перемещая любые повторяющиеся вхождения в конец массива.

Это можно сделать таким образом? Если да, каким будет алгоритм после получения сортированного массива пузырьков. Или есть лучший способ добиться этого.

Answer 1

Вы можете провести сортировку пузырьков за два прохода.

На первом этапе найдите наименьший элемент и поместите его в первую очередь. Затем найдите элемент, который находится больше, чем последний найденный элемент, но самый маленький из числа лотов и поставил его на второе место.

Выполните вышеуказанное, пока не достигнете максимального элемента.

Как только вы достигнете максимального элемента, пузырь сортировки на оставшейся части массива обычно.

Порядок сложности: точно в соответствии с сортировкой пузыря, поскольку вы просто делите его на две половины.

Полный рабочий код в C++:

#include <iostream> 


using namespace std; 

int main() 
{ 
    int arr[] = {2, 3, 4, 1, 9, 5, 1, 2, 6, 8, 1, 3}; 
    int size = 12; 
    // find max element. 
    int max = -1; 
    for (int I = 0; I < size; I++) { 
     if (arr[I] > max) 
     max = arr[I]; 
    } 


    int begin = 0; 
    bool maxPlaced = false; 
    int lastFound = -1; 
    while (!maxPlaced) { 

     // find the first element from the end, 
     // that is greater than elements already placed. 
     int end = size-1; 
     while (arr[end] <= lastFound) 
      end--; 

     for (int I = end; I > begin; I--) { 

     // swap if arr[i-1] is higher than arr[i] 
     // or arr[i-1] is a number that we have already placed. 
     if (arr[I] < arr[I-1] || lastFound >= arr[I-1]) { 
      int temp = arr[I]; 
      arr[I] = arr[I-1]; 
      arr[I-1] = temp; 
     } 
     } 
     // lastfound is the highest number that we have placed till now. 
     lastFound = arr[begin]; 
     begin++; 
     if (lastFound == max) 
     maxPlaced = true; 

    } 

    //continue bubble sort from begin position. 
    for (int I = begin; I < size; I++) { 
     for (int j = begin; j < size - 1 - (I-begin); j++) { 
     if (arr[j] > arr[j+1]) { 
      int temp = arr[j]; 
      arr[j] = arr[j+1]; 
      arr[j+1] = temp; 
     } 
     } 
    } 

    for (int i = 0; i < size; i++) 
     cout << arr[i] << " "; 

    return 0; 
} 

Выход:

1 2 3 4 5 6 7 8 9 1 1 2 3 

Для ввода {4,5,6,1,1,3,3,4,4,4,1,9,9,8,8}

Выход:

1 3 4 5 6 8 9 1 1 3 4 4 4 8 9 

Answer 2

Имейте в виду, что пузырь, так rt - наименее эффективный алгоритм сортировки тех, о которых вы упомянули.
Это O(n2) средний случай, а остальные O(n log n).

Heap сортировка

Разновидность heap-sort приходит на ум в качестве эффективного (O(n log n)) способа сделать это.

• Постройте кучу предметов.

• Имейте левый и правый итератор в массив, указывая на самые левые и правые позиции соответственно.

• Пока куча не пусто:

  • Удалить максимум.

  • Если удаленный элемент совпадает с последним удаленным элементом, вставьте его в правый итератор и уменьшите итератор.

  • В противном случае вставьте его в левый итератор и увеличьте итератор.

Теперь, если элементы в конце должны быть отсортированы так, просто обратным порядок (они должны быть в обратном порядке в конце вышеописанного процесса).

В месте альтернативы - выбор рода

Selection sort находит максимальный элемент на каждом шаге, так что это может быть легко изменен, чтобы пропустить применимые элементы, если они больше, чем уже найденного элемента.

Это можно сделать на месте (где выше не может), но снова O(n2).

int arr[] = {2, 3, 4, 1, 9, 5, 1, 2, 6, 8, 1, 3}; 
int arrLength = 12; 
for (int i = 0; i < arrLength; i++) 
{ 
    int minPos = -1; 
    for (int j = i; j < arrLength; j++) 
     // either it's the first element, or it's greater than the last element 
     // and either it's the first such element we find, or smaller than the best one 
     if ((i == 0 || arr[j] > arr[i-1]) && 
      (minPos == -1 || arr[j] < arr[minPos])) 
     { 
     minPos = j; 
     } 

    // no more elements to sort 
    if (minPos == -1) 
     break; 

    int temp = arr[i]; 
    arr[i] = arr[minPos]; 
    arr[minPos] = temp; 
} 

Live demo.

Если повторяющиеся элементы также нужно сортировать, это необходимо будет сделать дополнительно (с любым методом сортировки).