GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — java-basics/java-programs/QuickSort.java at master · learning-zone/java-basics

Expand file tree

/

QuickSort.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
71 lines (66 loc) · 1.58 KB
/

QuickSort.java

Copy path

File metadata and controls

71 lines (66 loc) · 1.58 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
package misc;
import java.util.Arrays;
import java.util.Stack;
public class QuickSort {
/**
* Iterative implementation of QuickSort sorting algorithm.
*
* */
public static void iterativeQuickSort(int[] numbers) {
Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(numbers.length);
while(!stack.isEmpty()) {
int end = (int) stack.pop();
int start = (int) stack.pop();
if(end - start < 2) {
continue;
}
int p = start + ((end - start) / 2);
p = partition(numbers, p, start, end);
stack.push(p + 1);
stack.push(end);
stack.push(start);
stack.push(p);
}
}
/**
* Utility method to partition the array into smaller array, and
* comparing numbers to rearrange them as per QuickSort algorithm.
**/
private static int partition(int[] input, int position, int start, int end) {
int l = start;
int h = end - 2;
int piv = input[position];
swap(input, position, end - 1);
while(l < h) {
if(input[l] < piv) {
l++;
} else if(input[h] >= piv) {
h--;
} else {
swap(input, l, h);
}
}
int idx = h;
if(input[h] < piv) {
idx++;
}
swap(input, end - 1, idx);
return idx;
}
/**
* Utility method to swap two numbers
**/
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] array = {34, 32, 43, 12, 11, 32, 22, 21, 32};
System.out.println("Before Sorting: " + Arrays.toString(array));
iterativeQuickSort(array);
System.out.println("After Sorting: " + Arrays.toString(array));
}
}
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.