Skip to main content

Quick Sort In Java

Question


  • You are given an array(arr) of integers.
  • You have to sort the given array in increasing order using quicksort.

Input Format

An Integer n
arr1
arr2..
n integers

Constraints

1 <= N <= 100000
-10^9 <= arr[i] <= 10^9

Sample Input

5
7
-2
4
1
3

Sample Output

pivot -> 3
Swapping -2 and 7
Swapping 1 and 7
Swapping 3 and 4
pivot index -> 2
pivot -> 1
Swapping -2 and -2
Swapping 1 and 1
pivot index -> 1
pivot -> -2
Swapping -2 and -2
pivot index -> 0
pivot -> 4
Swapping 4 and 7
pivot index -> 3
pivot -> 7
Swapping 7 and 7
pivot index -> 4
-2 1 3 4 7

Program

import java.io.*;
import java.util.*;

public class Main {

  public static void quickSort(int[] arr, int lo, int hi) {
    //write your code here
    if(lo > hi){
        return;
    }
    
    int pivot = arr[hi];
    int pidex = partition(arr, pivot, lo, hi);
    quickSort(arr, lo, pidex - 1);
    quickSort(arr, pidex + 1, hi);
  }

  public static int partition(int[] arr, int pivot, int lo, int hi) {
    System.out.println("pivot -> " + pivot);
    int i = lo, j = lo;
    while (i <= hi) {
      if (arr[i] <= pivot) {
        swap(arr, i, j);
        i++;
        j++;
      } else {
        i++;
      }
    }
    System.out.println("pivot index -> " + (j - 1));
    return (j - 1);
  }

  // used for swapping ith and jth elements of array
  public static void swap(int[] arr, int i, int j) {
    System.out.println("Swapping " + arr[i] + " and " + arr[j]);
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  public static void print(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  public static void main(String[] args) throws Exception {
    Scanner scn = new Scanner(System.in);
    int n = scn.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = scn.nextInt();
    }
    quickSort(arr, 0, arr.length - 1);
    print(arr);
  }

}

Comments

  1. Anonymous2/07/2022

    This comment has been removed by a blog administrator.

    ReplyDelete

Post a Comment

Thanks for the comment.

Popular posts from this blog

Tic Tac Toe Python 3: The Standard Tic-Tac-Toe Game in Python 3

I just finished Tic tac toe game as my first python project. This is a very simple classic game, for beginners in programming tic-tac-toe game is the best choice. I am using Jupyter notebook, you can use any python ide like Pycharm, Spyder etc. Scenario of tic-tac-toe game: Your task is to write a simple program which pretends to play  Tic-tac-toe game with the user.  To make it easier for you. We have decided to simplify the game. Here are our assumptions. the computer should play a game using 'X' the user should play a game using 'O' the first move belongs to the computer, it always 'X' in the middle of the board.  all squares are numbered row by row, start with '1'. the user move is to enter the number of the square they choose, the number must be valid, that is it must be an integer, it must be greater than  0 and less than 10, and it cannot point to a field which is already occupied. the program checks the ga

Prime Number Program in Java: Is Number Prime Or Not

Question You've to check whether a given number is prime or not. Take a number "t" as input representing a count of input numbers to be tested. Take a number "n" as input "t" number of times. For each input value of n, print "prime" if the number is prime and "not prime" otherwise. Input Format A number t A number n A number n .. t number of times Output Format prime not prime not prime .. t number of times Constraints 1 <= t <= 10000 2 <= n < 10^9 Sample Input 5 19 21 33 37 121 Sample Output prime not prime not prime prime not prime Program import java.util.*; public class Main{ public static void main(String[] args) { Scanner scn = new Scanner(System.in); int t = scn.nextInt(); for(int i=0;i<t;i++){ int n = scn.nextInt(); int count = 0; for(int div=2;div*div<=n; div++){ if (n % div == 0){