Sắp xếp chèn (Insertion Sort) trong java

Định nghĩa sắp xếp chèn: Xét danh sách con gồm k phần tử đầu a1 … ak. Với k = 1, danh sách gồm một phần tử đã được sắp xếp thành dãy tăng dần. Giả sử trong danh sách k-1 phần tử đầu a1 … ak-1 đã được sắp xếp. Để sắp xếp phần tử ak = x ta tìm vị trí thích hợp của nó trong dãy a1 … ak-1. Vị trí thích hợp cần tìm là vị trí đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.

ví dụ: sử dụng thuật toán Insertion Sort sắp xếp dãy số theo thứ tự tăng dần.

Input: 18 9 33 4 84 32

Output: 4 9 18 32 33 84

Sắp xếp chèn (Insertion Sort)

Chương trình sau dãy số theo tứ tự tăng dần bằng thuật toán sắp xếp chèn:

package com.hiepsiit.baitap;

import java.util.Scanner;

public class insertionSort {
	
	private static void nhap_mang(int []A, int n) {
		Scanner scn =  new Scanner(System.in);
		for(int i=0; i<n; i++) {
			System.out.print("A[ "+i+" ]: ");
			A[i] = scn.nextInt();
		}
	}
	
	private static void xuat_mang(int []A, int n) {
		for(int i=0; i<n; i++) {
			System.out.println("A[ "+i+" ]: "+A[i]);
		}
	}
	
	private static void sap_xep_chen(int []A, int n) {
		for(int i=1; i<n; i++) {
			int x = A[i];
			int y = i;
			while( y > 0 && A[ y - 1 ] > x ) {
				A[y]=A[y-1];
				y--;
			}
			A[y]=x;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int []A;
		int n=0;
		Scanner scn = new Scanner(System.in);
		System.out.print("Nhập số: ");
		n = scn.nextInt();
		A = new int[n];
		nhap_mang(A, n);
		System.out.println("Mảng sau khi sắp xếp (Insertion Sort)");
		sap_xep_chen(A, n);
		xuat_mang(A, n);
	}

}

Kết quả:

​​​​​​​