Java finding the smallest integer in a speciofic position in a sets of integer

Question

Algorithm:

Procedure SELECT( k,S)
{ if ISI =1 then return the single element in S
   else { choose an element a randomly from S;
              let S1,S2,and S3 be he sequences of elements in S  
              less than, equal to, and greater than m, respectively;
             if IS1I >=k then return SELECT(k,S1)
              else
                   if (IS1I + IS2I >=k then return m
                   else return SELECT(k-IS1I-IS2I , S3);
             }
}

The question is to implement the first algorithm for finding the kth smallest integer in a set of integers and test your program for different sets of integers generated by a random number generator. Below is my solution.

import java.util.Random;
import java.util.Scanner;

public class main {
    private static Random rand = new Random();
    private static Scanner keyboard = new Scanner(System.in);

    public static int firstAlgorithm(int k, int[] S) {
        int m = S[rand.nextInt(S.length)];
        int[] S1 = new int[S.length];
        int[] S2 = new int[S.length];
        int[] S3 = new int[S.length];
        int p = 0;
        int q = 0;
        int r = 0;

        if (S.length == 1)
            return S[0];

        for (int i = 0; i < S.length; i++) {
            if (S[i] < m) {
                S1[p] = S[i];
                p++;
            } else if (S[i] == m) {
                S2[q] = S[i];
                q++;
            } else {
                S3[r] = S[i];
                r++;
            }
        }

        S1 = trimToSize(S1, p);
        S2 = trimToSize(S2, q);
        S3 = trimToSize(S3, r);

        if (S1.length >= k)
            return firstAlgorithm(k, S1);
        else if (S1.length + S2.length >= k)
            return m;
        else
            return firstAlgorithm(k - S1.length - S2.length, S3);
    }

    private static int[] trimToSize(int[] arr, int size) {
        int[] temp = new int[size];
        for (int i = 0; i < size; i++) {
            temp[i] = arr[i];
        }
        return temp;
    }

    public static void printArray(int[] S) {
        for (int i = 0; i < S.length; i++) {
            System.out.print(S[i] + "\t");
            if (i % 10 == 9)
                System.out.println();
        }
    }

    // start main method
    public static void main(String[] args) {
        System.out.print("Enter the size of an array: ");
        int size = keyboard.nextInt();
        while (size < 1) {
            System.out.println("Size of the array should be greater than 0.");
            System.out.print("Enter the size of an array: ");
            size = keyboard.nextInt();
        }

        System.out.print("Enter the value of k: ");
        int k = keyboard.nextInt();
        while (k < 1 || k > size) {
            System.out.println("Value of k should be in the range 1-" + size + ".");
            System.out.print("Enter the value of k: ");
            k = keyboard.nextInt();
        }

        int[] S = new int[size];
        for (int i = 0; i < size; i++) {
            S[i] = 100 + rand.nextInt(900);
        }

        System.out.println("\nRandom values generated in the array:");
        printArray(S);
        System.out.println();
        System.out.println(k + "th smallest value in the array using Algorithm #1: " + firstAlgorithm(k, S));

    }
}

But I need to implement the above algorithm without using a temporary array for partitioning. How can I do it?

Answer 1

The algorithm is Dijkstra's 3-way partition.

You will have to modify the original S.

Untested (pseudo) code ahead

public static int partition(int left, int right, int[] S) {
  int m = rand.nextInt(right-left);  // protect against malicious data
  swap(S[left+m], S[right]);
  int equal = left;

  while (left < right) {
    if (a[left] < a[n])
      swap(S, left++, equal++)
    else if (a[left] == a[n]) 
      swap(S, left, --right);
    else 
      left++;
  }

  return left, equal;
}


public static int firstAlgorithm(int k, int left, int right, int[] S) {
  if (left == right)
     return S[left];

  int p, e = partition(left, right, S); // returns 2 values. S1=[0,p), S2=[p,e), S3=[e, n)

  if (p >= k)
    return firstAlgorithm(k, left, p, S);
  else if (e >= k)  // p < k
     return S[p]; // p is the first equal, e is first larger than equal
  else // e < k
    return firstAlgorithm(k, e, right, S);
}


// test
S = {1, 4, 2, 6, 2};
k = 2;
int result = firstAlgorithm(2, 0, S.length-1, S);
assert(result == 2);

Warning syntax and off-by-one errors guarantied.

See here multiple ways to return 2 values in java.