Hoare Partition (A[L . . R]) // Partitions a sub-array by Hoares algorithm, usin

Question

Hoare Partition (A[L . . R])

// Partitions a sub-array by Hoares algorithm, using the first element as a pivot.

// Input: Sub-array of array A[0 . . n-1], defined by its left and right indices L and R

// (L < R)

// Output: Partition of A[L . . R], with the split position returned as this functions

// value

p = A[L]

i = L; j = R+1

repeat

   repeat i = i + 1 until A[ i ] >= p

   repeat j = j - 1 until A[ j ] <= p

   if i < j

       swap ( A[ i ], A[ j ] )

until i >= j

swap ( A[ L ], A[ j ] )   // place the pivot in the split position separating the

    // values smaller than or equal to the pivot from those

    // values larger than or equal to the pivot

return j

Hoare Partition Perform a Hoare Partition on the following array.

Place your partition in the array below. Your split position is index = ________________

Scrap

Index 0 1 2 3 4 5 6 7 8 9 10 11 Value 71 77 66 82 55 66 37 93 81 32 43 75

Explanation / Answer

I have entered the array elements as mentioned in the question.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;

public class HoareSort
{
public HoareSort()
{
System.out.println("Hoare Sort");

System.out.println("Enter number of elements in the array");
int array_elements = 2;
try
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
array_elements = Integer.parseInt(reader.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}

if (array_elements < 2)
{
System.out.println("Number of elements in the array should be greater or equal 2");
}
else
{
Random random = new Random();

//int[] A = new int[]{71, 77, 66, 82, 55, 66, 37, 93, 81, 32, 43, 75};
int[] A = new int[array_elements];

for (int i = 0; i < A.length; i++)
A[i] = random.nextInt(1000);

System.out.println("Unsorted array");
for (int i : A)
{
System.out.print(String.format("%5d", i));
}
System.out.println();

hoaresort(A, 0, A.length - 1);

System.out.println("Sorted array");
for (int i : A)
{
System.out.print(String.format("%5d", i));
}
System.out.println();
}
}

private void hoaresort(int[] A, int p, int r)
{
int q;
if (p < r)
{
q = hoare_partition(A, p, r);
hoaresort(A, p, q - 1);
hoaresort(A, q + 1, r);
}
}

private int hoare_partition(int[] A, int p, int r)
{
int x = A[p];
int i = p - 1;
int j = r + 1 ;

int exchange;

while (true)
{
do
{
j--;
}
while (A[j] > x);

do
{
i++;
}
while (A[i] < x);

if (i < j)
{
exchange = A[i];
A[i] = A[j];
A[j] = exchange;
}
else
return j;
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.