-
Notifications
You must be signed in to change notification settings - Fork 55
Expand file tree
/
Copy pathpartition.java
More file actions
89 lines (85 loc) · 3.68 KB
/
partition.java
File metadata and controls
89 lines (85 loc) · 3.68 KB
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
// partition.java
// demonstrates partitioning an array
// to run this program: C>java PartitionApp
////////////////////////////////////////////////////////////////
class ArrayPar
{
private long[] theArray; // ref to array theArray
private int nElems; // number of data items
//--------------------------------------------------------------
public ArrayPar(int max) // constructor
{
theArray = new long[max]; // create the array
nElems = 0; // no items yet
}
//--------------------------------------------------------------
public void insert(long value) // put element into array
{
theArray[nElems] = value; // insert it
nElems++; // increment size
}
//--------------------------------------------------------------
public int size() // return number of items
{ return nElems; }
//--------------------------------------------------------------
public void display() // displays array contents
{
System.out.print("A=");
for(int j=0; j<nElems; j++) // for each element,
System.out.print(theArray[j] + " "); // display it
System.out.println("");
}
//--------------------------------------------------------------
public int partitionIt(int left, int right, long pivot)
{
int leftPtr = left - 1; // right of first elem
int rightPtr = right + 1; // left of pivot
while(true)
{
while(leftPtr < right && // find bigger item
theArray[++leftPtr] < pivot)
; // (nop)
while(rightPtr > left && // find smaller item
theArray[--rightPtr] > pivot)
; // (nop)
if(leftPtr >= rightPtr) // if pointers cross,
break; // partition done
else // not crossed, so
swap(leftPtr, rightPtr); // swap elements
} // end while(true)
return leftPtr; // return partition
} // end partitionIt()
//--------------------------------------------------------------
public void swap(int dex1, int dex2) // swap two elements
{
long temp;
temp = theArray[dex1]; // A into temp
theArray[dex1] = theArray[dex2]; // B into A
theArray[dex2] = temp; // temp into B
} // end swap()
//--------------------------------------------------------------
} // end class ArrayPar
////////////////////////////////////////////////////////////////
class PartitionApp
{
public static void main(String[] args)
{
int maxSize = 16; // array size
ArrayPar arr; // reference to array
arr = new ArrayPar(maxSize); // create the array
for(int j=0; j<maxSize; j++) // fill array with
{ // random numbers
long n = (int)(java.lang.Math.random()*199);
arr.insert(n);
}
arr.display(); // display unsorted array
long pivot = 99; // pivot value
System.out.print("Pivot is " + pivot);
int size = arr.size();
// partition array
int partDex = arr.partitionIt(0, size-1, pivot);
System.out.println(", Partition is at index " + partDex);
arr.display(); // display partitioned array
} // end main()
} // end class PartitionApp
////////////////////////////////////////////////////////////////