stoyanoff

array-sort

Sep 18th, 2020 (edited)
954
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. class QuickSort {
  4.     //selects last element as pivot, pi using which array is partitioned.
  5.     int partition(int intArray[], int low, int high) {
  6.         int pi = intArray[high];
  7.         int i = (low - 1); // smaller element index
  8.         for (int j = low; j < high; j++) {
  9.             // check if current element is less than or equal to pi
  10.             if (intArray[j] <= pi) {
  11.                 i++;
  12.                 // swap intArray[i] and intArray[j]
  13.                 int temp = intArray[i];
  14.                 intArray[i] = intArray[j];
  15.                 intArray[j] = temp;
  16.             }
  17.         }
  18.  
  19.         // swap intArray[i+1] and intArray[high] (or pi)
  20.         int temp = intArray[i + 1];
  21.         intArray[i + 1] = intArray[high];
  22.         intArray[high] = temp;
  23.  
  24.         return i + 1;
  25.     }
  26.  
  27.  
  28.     //routine to sort the array partitions recursively
  29.     void quick_sort(int intArray[], int low, int high) {
  30.         if (low < high) {
  31.             //partition the array around pi=>partitioning index and return pi
  32.             int pi = partition(intArray, low, high);
  33.  
  34.             // sort each partition recursively
  35.             quick_sort(intArray, low, pi - 1);
  36.             quick_sort(intArray, pi + 1, high);
  37.         }
  38.     }
  39. }
  40.  
  41. class Main {
  42.     public static void main(String args[]) {
  43.        
  44.      //initialize a numeric array, with random numbers from 1-100
  45.  
  46.         int myArraySize = 100;
  47.         int[] myArray = new int[myArraySize];
  48.         for (int i = 0; i < myArraySize; i++) {
  49.  
  50.             myArray[i] = (int) ((Math.random() * 100) + 1);
  51.  
  52.  
  53.         }
  54.         int n = myArray.length;
  55.         //print the original array
  56.         System.out.println("Original Array: " + Arrays.toString(myArray));
  57.         //call quick_sort routine using QuickSort object
  58.         QuickSort obj = new QuickSort();
  59.         obj.quick_sort(myArray, 0, n - 1);
  60.         //print the sorted array
  61.         System.out.println("\nSorted Array: " + Arrays.toString(myArray));
  62.     }
  63. }
RAW Paste Data