Home Sorting algorithm
Post
Cancel

Sorting algorithm

In this post, it includes the following sorting algorithms. The code is self explained.

  • selection sort
  • insert sort
  • bubble sort
  • quick sort
  • merge sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
import java.util.Arrays;

public class Sort {
	public static void selection_sort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int min_idx = i;

			// find the minimum value from right of arr[i] and swap with arr[i]
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[min_idx]) {
					min_idx = j;
				}
			}

			// move the min value to the beginning of array
			int temp = arr[i];
			arr[i] = arr[min_idx];
			arr[min_idx] = temp;
		}
	}

	public static void insert_sort(int[] arr) {
		// sort from the second element since the first one is already sorted for itself
		for (int i = 1; i < arr.length; i++) {
			int curr = arr[i];
			int j = i - 1;

			// move all the greater values(than curr) to one position right
			while (j >= 0 && arr[j] > curr) {
				arr[j + 1] = arr[j];
				j--;
			}

			arr[j + 1] = curr;
		}
	}

	public static void bubble_sort(int[] arr) {
		// bubble sort for n - 1 rounds
		for (int i = 0; i < arr.length - 1; i++) {
			boolean swapped = false;
			// For each round, bubble up the maximum element to the right
			for (int j = 0; j < arr.length - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
					swapped = true;
				}
			}

			if (!swapped)
				break;
		}
	}

	public static void quick_sort(int[] arr, int left, int right) {
		if (left < right) {
			int pivot = partition(arr, left, right);
			quick_sort(arr, left, pivot - 1);
			quick_sort(arr, pivot + 1, right);
		}
	}

	private static int partition(int[] arr, int left, int right) {
		int pivot = arr[right];
		int curr = left - 1;

		for (int i = left; i < right; i++) {
			if (arr[i] <= pivot) {
				curr++;
				int temp = arr[curr];
				arr[curr] = arr[i];
				arr[i] = temp;
			}
		}

		curr++;
		int temp = arr[curr];
		arr[curr] = pivot;
		arr[right] = temp;
		return curr;
	}

	public static void merge_sort(int[] arr, int left, int right) {
		if (left < right) {
			//int mid = (left + right) / 2;
			int mid = left + (right - left) / 2; // avoid overflow
			merge_sort(arr, left, mid);
			merge_sort(arr, mid + 1, right);
			merge(arr, left, mid, right);
		}
	}

	private static void merge(int[] arr, int left, int mid, int right) {
		int l1 = mid - left + 1;
		int l2 = right - mid;

		// copy left and right to the temporary array
		int[] a1 = new int[l1];
		int[] a2 = new int[l2];


		for (int i = 0; i < l1; i++) {
			a1[i] = arr[left + i];
		}

		for (int i = 0; i < l2; i++) {
			a2[i] = arr[mid + 1 + i];
		}

		// merge back to the original array
		int i = 0, j = 0, k = left;
		while (i < l1 && j < l2) {
			if (a1[i] <= a2[j]) {
				arr[k++] = a1[i++];
			} else {
				arr[k++] = a2[j++];
			}
		}

		while (i < l1) {
			arr[k++] = a1[i++];
		}
		while (j < l2) {
			arr[k++] = a2[j++];
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = { 11, 25, 12, 22, 64 };
		selection_sort(arr);
		System.out.println(Arrays.toString(arr));

		int[] arr1 = { 11, 25, 12, 22, 64 };
		insert_sort(arr1);
		System.out.println(Arrays.toString(arr1));

		int[] arr2 = { 11, 25, 12, 22, 64 };
		bubble_sort(arr2);
		System.out.println(Arrays.toString(arr2));

		int[] arr3 = { 11, 25, 12, 22, 64 };
		quick_sort(arr3, 0, arr3.length - 1);
		System.out.println(Arrays.toString(arr3));

		int[] arr4 = { 11, 25, 12, 22, 64 };
		merge_sort(arr4, 0, arr4.length - 1);
		System.out.println(Arrays.toString(arr4));
	}

}
This post is licensed under CC BY 4.0 by the author.

Thread synchronization

Tuning kernel parameters in Docker

Comments powered by Disqus.