Insertion Sort Algorithm буюу Нэмж Жагсаах Алгоритм

void insertionsort(int * input, int n) {
     int j;
     int i;
     int key;
     for(j=1; j < n; j++) {
        key = input[j];
        i = j-1;
        while(i >= 0 && input[i] > key) {
            input[i+1] = input[i];
            i--;
        }
        input[i+1] = key;
     }
}

int main() {
    int i;
    int array[] = {9,8,7,6,4,2};

    insertionsort(&array, 6);
    for (i=0; i<6; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    system("PAUSE");
    return 0;
}

Дээрх алгоритм нь массивт байгаа тоонуудыг хоёр дахиас нь эхлэн тоо тус бүрийг өмнөх тоонуудтай нь харицуулан өмнөх тооноосоо бага бол байрыг нь сольж үргэлжлүүлэн итерацаар ажилна.

Хамгийн муугаар бодож байж алгоритмын үнэ цэнийг олж авна. Жишээ нь дээрх “нэмж жагсаах” алгоритмийн хувьд массив дахь тоонууд эсрэгээрээ (ихээсээ багаруу) жагсаагдсан байрлалтай бол n2 үйлдлийн дараа алгоритм ажилаа хийж дуусан байна. Өөрөө хэлбэл O(n2).