Revision of HeapSort.java

1 file changed, 72 insertions

HeapSort.java(fichier créé)

		@@ -0,0 +1,72 @@
1	+	import java.util.*;
2	+	public class HeapSort {
3	+	public void sort(int arr[])
4	+	{
5	+	int N = arr.length;
6	+
7	+	for (int i = N / 2 - 1; i >= 0; i--)
8	+	heapify(arr, N, i);
9	+
10	+	for (int i = N - 1; i > 0; i--) {
11	+
12	+	int x = arr[0];
13	+	arr[0] = arr[i];
14	+	arr[i] = x;
15	+
16	+	heapify(arr, i, 0);
17	+	}
18	+	}
19	+
20	+	void heapify(int arr[], int N, int i)
21	+	{
22	+	int largest = i;
23	+	int l = 2 * i + 1;
24	+	int r = 2 * i + 2;
25	+
26	+	if (l < N && arr[l] > arr[largest])
27	+	largest = l;
28	+
29	+	if (r < N && arr[r] > arr[largest])
30	+	largest = r;
31	+
32	+	if (largest != i) {
33	+	int swap = arr[i];
34	+	arr[i] = arr[largest];
35	+	arr[largest] = swap;
36	+
37	+	heapify(arr, N, largest);
38	+	}
39	+	}
40	+	static void printArray(int arr[])
41	+	{
42	+	int N = arr.length;
43	+
44	+	for (int i = 0; i < N; ++i)
45	+	System.out.print(arr[i] + " ");
46	+	System.out.println();
47	+	}
48	+
49	+	public static void main(String args[])
50	+	{
51	+	int i, n, arr[];
52	+
53	+	Scanner s = new Scanner(System.in);
54	+	System.out.println("Enter no. of elements in aray:");
55	+	n = s.nextInt();
56	+
57	+	arr = new int[n];
58	+
59	+	System.out.println("Enter " + n + " integers:");
60	+
61	+	for (i = 0;i<n; i++)
62	+	arr[i] = s.nextInt();
63	+
64	+	HeapSort ob = new HeapSort();
65	+	ob.sort(arr);
66	+
67	+	System.out.println("Sorted array is");
68	+	printArray(arr);
69	+	}
70	+
71	+
72	+	}

Plus récent Plus ancien