Algorithm(thuật toán) - Lập Trình C# PHP C++ Java Python

Insertion sortÝ tưởng của insertion sort như sếp bài nếu số phía sau nhỏ hơn phía trước thì cho thì cho nó lên trên.

Tư tưởng của thuật toán là i, j để chỉ vị trí, ví dụ j=2 tức là vị trí thứ 2
INSERTION-SORT.A/
for j = 2 to A:length
key = A[j]
// Insert A[j] into the sorted sequence A[1.. j - 1].
i = j - 1
while i > 0 and A[i] > key
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key

Tư tưởng của thuật toán là i, j để chỉ vị trí, ví dụ j=2 tức là vị trí thứ 2

INSERTION-SORT.A/

for j = 2 to A:length

key = A[j]

// Insert A[j] into the sorted sequence A[1.. j - 1].

i = j - 1

while i > 0 and A[i] > key

A[i + 1] = A[i]

i = i - 1

A[i + 1] = key

Cách thực hiện như sau

void insertionSort(int arr[], int n) 
{ 
int i, key, j; 
for (i = 1; i < n; i++) { 
key = arr[i]; 
j = i - 1; 
/* Move elements of arr[0..i-1], that are 
greater than key, to one position ahead 
of their current position */
while (j >= 0 && arr[j] > key) { 
arr[j + 1] = arr[j]; 
j = j - 1; 
} 
arr[j + 1] = key; 
} 
}

void insertionSort(int arr[], int n)

{

int i, key, j;

for (i = 1; i < n; i++) {

key = arr[i];

j = i - 1;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead

of their current position */

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j = j - 1;

}

arr[j + 1] = key;

}

About The Author