Алгоритам сортирања уметања

У овом упутству ћете научити како функционише сортирање уметања. Такође, наћи ћете радне примере сортирања уметања у Ц, Ц ++, Јава и Питхон.

Сортирање уметања делује слично као што сортирамо карте у руци у карташкој игри.

Претпостављамо да је прва картица већ сортирана, тада бирамо неразврстану картицу. Ако је неразврстана карта већа од картице у руци, она се иначе поставља десно, лево. На исти начин се узимају и друге несортиране карте и постављају се на своје право место.

Сличан приступ користи се сортирањем уметања.

Сортирање уметања је алгоритам сортирања који поставља несортирани елемент на одговарајуће место у свакој итерацији.

Како сортирање уметања функционише?

Претпоставимо да треба да сортирамо следећи низ.

Почетни низ
  1. Претпоставља се да је први елемент у низу сортиран. Узмите други елемент и одложите га одвојено у key.
    Упоредите keyса првим елементом. Ако је први елемент већи од key, тада се кључ поставља испред првог елемента. Ако је први елемент већи од кључа, тада се кључ поставља испред првог елемента.
  2. Сада су прва два елемента сортирана.
    Узмите трећи елемент и упоредите га са елементима лево од њега. Поставио га је одмах иза елемента мањег од њега. Ако нема елемента мањег од њега, ставите га на почетак низа. Место 1 на почетку
  3. Слично томе, сваки несортирани елемент поставите на тачан положај. Место 4 иза 1 Место 3 иза 1 и низ је сортиран

Алгоритам сортирања уметања

 инсертионСорт (арраи) означи први елемент сортираним за сваки несортирани елемент Кс 'извади' елемент Кс за ј Кс помери сортирани елемент удесно за 1 прекидну петљу и убаци Кс овде заврши инсертионСорт

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц ++ 
 # Insertion sort in Python def insertionSort(array): for step in range(1, len(array)): key = array(step) j = step - 1 # Compare key with each element on the left of it until an element smaller than it is found # For descending order, change keyarray(j). while j>= 0 and key < array(j): array(j + 1) = array(j) j = j - 1 # Place key at after the element just smaller than it. array(j + 1) = key data = (9, 5, 1, 4, 3) insertionSort(data) print('Sorted Array in Ascending Order:') print(data)
  // Insertion sort in Java import java.util.Arrays; class InsertionSort ( void insertionSort(int array()) ( int size = array.length; for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (j>= 0 && key < array(j)) ( array(j + 1) = array(j); --j; ) // Place key at after the element just smaller than it. array(j + 1) = key; ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 5, 1, 4, 3 ); InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
 // Insertion sort in C #include // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( printf("%d ", array(i)); ) printf(""); ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); printf("Sorted array in ascending order:"); printArray(data, size); )
 // Insertion sort in C++ #include using namespace std; // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); cout << "Sorted array in ascending order:"; printArray(data, size); )

Сложеност

Сложеност времена

  • Најгоре сложеност случаја: Претпоставимо да је низ у растућем редоследу и желите да га сортирате у опадајућем редоследу. У овом случају долази до најгорег сложености случаја. Сваки елемент се мора упоређивати са свим осталим елементима, тако да се за сваки н-ти елемент врши поређење. Дакле, укупан број поређења =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Најбоља сложеност случаја: O(n)
    Када је низ већ сортиран, спољна петља се покреће nнеколико пута, док се унутрашња петља уопште не покреће. Дакле, постоји само nвелики број поређења. Дакле, сложеност је линеарна.
  • Просечна сложеност случаја: Појављује се када су елементи низа помешаним редоследом (ни растући ни силазни).O(n2)

Сложеност простора

Сложеност простора је O(1)зато што се користи додатна променљива key.

Апликације за сортирање уметања

Сорта уметања се користи када:

  • низ има мали број елемената
  • остало је само неколико елемената за сортирање

Занимљиви Чланци...