Java : Randomized Quick sort

/**
 * Created on 11-Aug-19 10:02 AM.
 *
 * @author Aayush
 */
public class RandomizedQuickSort {
    public static void sort(int[] array) {
        sort(array, 0, array.length-1);
    }

    public static void sort(int[] array, int startIndex, int endIndex){
        if(startIndex >= endIndex) return;
        int partitionIndex = partition(array, startIndex, endIndex);
        sort(array, startIndex, partitionIndex-1);
        sort(array, partitionIndex+1, endIndex);
    }

    /**
     * Returns the partition index, where the pivot element resides.
     * On the left of the pivot element, all the lower values reside.
     * On the right of the pivot element, all the higher values reside.
     *
     * @param array
     * @param startIndex
     * @param endIndex
     * @return
     */
    private static int partition(int[] array, int startIndex, int endIndex) {
        int randomIndex = getRandomNumber(startIndex, endIndex);
        int pivot = array[randomIndex]; // getting the random pivot
        array[endIndex] = swap(pivot, array[randomIndex] = array[endIndex]); //putting the random pivot at the end index
        int partitionIndex = startIndex;
        for (int i=startIndex; i<endIndex; i++) {
            if(array[i] <= pivot){
                array[i] = swap(array[partitionIndex], array[partitionIndex] = array[i]);
                partitionIndex++;
            }
        }
        array[partitionIndex] = swap(array[endIndex], array[endIndex] = array[partitionIndex]);
        return partitionIndex;
    }

    /**
     * A chucklesome swap function.
     *
     * E.g. to swap 'a' & 'b',
     * store the returned value of this method to 'a',
     * and call the method with values :
     * #swapValue = 'b' and #swapYourselfWhileCalling = 'b=a'
     *
     * @param swapValue Value that will be returned
     * @param swapYourselfWhileCalling swap the other way while calling
     * @return #swapValue
     */
    private static int swap(int swapValue, int swapYourselfWhileCalling){ return swapValue;}

    /**
     * Calculates a random value i.e.
     * greater than or equal to start and
     * less than end
     *
     * @param start
     * @param end
     * @return Returns a random number based on the above explanation
     */
    private static int getRandomNumber(int start, int end){
        int randomIndex;
        do{
            randomIndex = (int) (Math.random() * end);
        }while(randomIndex < start);
        return randomIndex;
    }
}

Currently the above handles integer sorting in ascending order. (I’ve chosen a basic one, so it would be easier to understand)
It can be upgraded to sort other types, and also the sorting order can be variable.
Any related questions, drop your question below.
Also, everyone loves appreciations 🙂

That’s All. P)
Happy Java-ing.

-Aayush Shrivastava

---

Name(required)

Email(required)

Happy with the content?

Yes

No

Feedback(required)

Submit

Δ

Java : Insertion Sort

/**
 * Created on 25-Jun-18 3:32 PM.
 *
 * @author Aayush
 */
public class InsertionSort {

  public static void sort(int[] array){
    for(int i=1; i<array.length; i++){
      moveToAppropriatePlace(array, i);
    }
  }

  /**
   * Pick a value at index @indexOfCurrentValue, and shift it backwards finding the appropriate place
   *
   * @param array
   * @param indexOfCurrentValue
   */
  private static void moveToAppropriatePlace(int[] array, int indexOfCurrentValue) {
    int currentValue = array[indexOfCurrentValue];
    int i = indexOfCurrentValue;
    while(i>0){
      if(array[i-1] > currentValue) array[i] = array[i-1];
      else break;
      i--;
    }
    if(i != indexOfCurrentValue) array[i] = currentValue;
  }
}

That’s All. P)
Happy Java-ing.

-Aayush Shrivastava

---

Name(required)

Email(required)

Are you satisfied?

Yes

No

Feedback(required)

Submit

Δ

Java : Bubble Sort

/**
 * Created on 25-Jun-18 12:34 PM.
 *
 * @author Aayush
 */
public class BubbleSort {
  public static void sort(int[] array){
    for(int i=array.length-1; i>=0; i--) {
      if(!moveHighestValueToEnd(array, i))
        break;
    }
  }

  /**
   * Moves the highest value to @endIndex in the array
   *
   * @param array
   * @param endIndex
   * @return
   */
  private static boolean moveHighestValueToEnd(int[] array, int endIndex){
    boolean flag = false;
    for(int i = 0; i < endIndex; i++){
      if(array[i] > array[i+1]) {
        int temp = array[i];
        array[i] = array[i+1];
        array[i+1] = temp;
        flag = true;
      }
    }
    return flag;
  }
}

That’s All. P)
Happy Java-ing.

-Aayush Shrivastava

---

Name(required)

Email(required)

Are you satisfied?

Yes

No

Feedback(required)

Submit

Δ

Java : Selection Sort

/**
 * Created on 25-Jun-18 11:56 AM.
 *
 * @author Aayush
 */
public class SelectionSort {

  public static void sort(int[] array){
    int size = array.length;
    for(int i=0; i<size-1; i++){
      int minIndex = findLeastValueIndex(array, i + 1);
      if(i != minIndex){
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
      }
    }
  }

  /**
   * Find the index of least value present in the range, from begin Index to end of Array
   *
   * @param array
   * @param beginIndex
   * @return
   */
  private static int findLeastValueIndex(int[] array, int beginIndex){
    int min = array[beginIndex - 1];
    int minIndex = beginIndex - 1;
    for(int i=beginIndex; i<array.length; i++)
      if(array[i] > 0 && array[i] < min) {
        min = array[i];
        minIndex = i;
      }
    return minIndex;
  }
}

That’s All. P)
Happy Java-ing.

-Aayush Shrivastava

---

Name(required)

Email(required)

Are you satisfied?

Yes

No

Feedback(required)

Submit

Δ

Java : Merge Sort

/**
 * Created on 25-Jun-18 7:41 PM.
 *
 * @author Aayush
 */
public class MergeSort {

  public static void sort(int[] array){
    if(array.length == 1) return;
    int halfSize = array.length/2;
    int[] leftArray = Arrays.copyOf(array, halfSize);
    int[] rightArray = Arrays.copyOfRange(array, halfSize, array.length);
    sort(leftArray);
    sort(rightArray);
    merge(leftArray, rightArray, array);
  }

  /**
   * Merge the left and right arrays, into the array
   *
   * @param leftArray
   * @param rightArray
   * @param array
   */
  private static void merge(int[] leftArray, int[] rightArray, int[] array){
    int arrayIndex = 0, leftIndex = 0, rightIndex = 0;

    while(leftIndex < leftArray.length && rightIndex < rightArray.length){
      if(leftArray[leftIndex] <= rightArray[rightIndex]){
        array[arrayIndex] = leftArray[leftIndex];
        leftIndex++;
      }
      else {
        array[arrayIndex] = rightArray[rightIndex];
        rightIndex++;
      }
      arrayIndex++;
    }

    while(leftIndex < leftArray.length){
      array[arrayIndex] = leftArray[leftIndex];
      leftIndex++;
      arrayIndex++;
    }

    while(rightIndex < rightArray.length){
      array[arrayIndex] = rightArray[rightIndex];
      rightIndex++;
      arrayIndex++;
    }

  }
}

That’s All. P)
Happy Java-ing.

-Aayush Shrivastava

---

Name(required)

Email(required)

Are you satisfied?

Yes

No

Feedback(required)

Submit

Δ

Java : Quick sort

/**
 * Created on 25-Jun-18 9:02 PM.
 *
 * @author Aayush
 */
public class QuickSort {

  public static void sort(int[] array) {
    sort(array, 0, array.length-1);
  }

  public static void sort(int[] array, int startIndex, int endIndex){
    if(startIndex >= endIndex) return;
    int partitionIndex = partition(array, startIndex, endIndex);
    sort(array, startIndex, partitionIndex-1);
    sort(array, partitionIndex+1, endIndex);
  }

  /**
   * This method finds the partition index.
   * On the left of the pivot element, all the lower values reside. 
   * On the right of the pivot element, all the higher values reside. 
   *
   * @param array
   * @param startIndex
   * @param endIndex
   * @return Returns the partition index, 
   * where the pivot element resides. 
   */
  private static int partition(int[] array, int startIndex, int endIndex) {
    int pivot = array[endIndex];
    int partitionIndex = startIndex;
    for (int i=startIndex; i<endIndex; i++) {
      if(array[i] <= pivot){
        array[i] = swap(array[partitionIndex], array[partitionIndex] = array[i]);
        partitionIndex++;
      }
    }
    array[partitionIndex] = swap(array[endIndex], array[endIndex] = array[partitionIndex]);
    return partitionIndex;
  }

    /**
     * A chucklesome swap function.
     *
     * E.g. to swap 'a' & 'b',
     * store the returned value of this method to 'a',
     * and call the method with values :
     * #swapValue = 'b' and #swapYourselfWhileCalling = 'b=a'
     *
     * @param swapValue Value that will be returned
     * @param swapYourselfWhileCalling swap the other way while calling
     * @return #swapValue
     */
    private static int swap(int swapValue, int swapYourselfWhileCalling){ return swapValue;}
}

That’s All. P)
Happy Java-ing.

-Aayush Shrivastava

---

Name(required)

Email(required)

Are you satisfied?

Yes

No

Feedback(required)

Submit

Δ

 

Java : Find Duplicate Elements in a List (without using Set)

import java.util.*;

public class Main{

  /* This method takes a list and changes it into a distinct list */
  public static <T> void distinctList(List<T> list){
    List<T> nonDistinctElements = new ArrayList<>();

    for(T s : list)
      if(list.indexOf(s) != list.lastIndexOf(s))
        nonDistinctElements.add(s);

    for(T nonDistinctElement : nonDistinctElements)
      if(list.indexOf(nonDistinctElement) != list.lastIndexOf(nonDistinctElement))
        list.remove(nonDistinctElement);
  }

  /* This method takes a list and returns a list of duplicate values */
  public static <T> List<T> findDuplicates(List<T> list){

    List<T> nonDistinctElements = new ArrayList<>();

    for(T s : list)
      if(list.indexOf(s) != list.lastIndexOf(s))
        if(!nonDistinctElements.contains(s))
          nonDistinctElements.add(s);

    return nonDistinctElements;
  }

  /* Main method for testing the above */
  public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    //Inserting "hello" 10 times
    for(int i=0; i<10; i++)
      list.add("hello");
    //Inserting "hi" 5 times
    for(int i=0; i<5; i++)
      list.add("hi");
    //Inserting "me" 3 times
    for(int i=0; i<3; i++)
      list.add("me");
    
    //Both the "findDuplicates" & "distinctList" methods are different methods, delegation can be done, 
    //but I've kept them separate, so both can be used independently
    System.out.println("Duplicate Values " + findDuplicates(list)); // printing the duplicates
    Main.distinctList(list); //creating a list with distinct values
    System.out.println("Distinct List : " + list);
  }
}

That’s All. P)
Happy Java-ing.

-Aayush Shrivastava

---

Name(required)

Email(required)

Are you satisfied?

Yes

No

Feedback(required)

Submit

Δ