Question

Write a java program that randomizes a list and sorts it.

1. The list will be randomized to be at least 12 elements and no more than 30 elements with values between 1 and 100.
2. You will submit one program with two sorts done separately within the program. The list will be re-randomized before reach sort.
3. Write a flowchart for each sort.

Answer 1

package sort;

import java.util.Random;

/*To avoid running inner loop even though array is sorted

* We can pass swapped flag inside if statement

* Initialize flag to false as not element has swapped before start swapping

* every time element get swapped set swapped flag to true

* after one iteration not single element swapped ie flag is false

* means array is swapped already no need to make another iteration

* get out of the loop

* this algorithm wont need (n^2) in best case

* in best case it perform result in even O(N) time

*/

public class BubbleSort {

public static void bubbleSort(int ar[]){

for(int i=0;i<ar.length;i++){

boolean swapped=false; //for each iteration set flag =false

for(int j=1;j<ar.length;j++){

if(ar[j-1]>ar[j]){

int temp=ar[j-1];

ar[j-1]=ar[j];

ar[j]=temp;

swapped=true; //if swapped flag =true

}

}

if(!swapped) //if not element swapped at all

break; //array is sorted get out of loop

}

}

public static int[] getRandomNumberArray(int arraySize ){

int ar[]=new int[arraySize];

Random rnd = new Random();

for(int i=0;i<ar.length;i++){

ar[i]= rnd.nextInt(100);

}

return ar;

}

public static void selSort(int[] arr){

  

for (int i=0;i<arr.length;i++)

{

   // int smallerNumber = arr[i]; //make current element as smallest

   int index=i; //initialize smallest i as -1

  

for(int j=i+1;j<arr.length;j++){ //find smallest element in ar[i.....n]

   if(arr[index]>arr[j]){

  

   index=j; //remember i of smallest

   }

   }

   if(index!=-1){ //if smallest found

   int smallerNumber=arr[i]; //swap it

   arr[i]=arr[index];

   arr[index] = smallerNumber;

   }

}

  

}

public static void main(String[] args) {

Random r=new Random();

int h=30;

int l=12;

int size=r.nextInt(h-l) + l; //no of element between 12 to 30

System.out.println("Normal array");

int ar[]=getRandomNumberArray(size);

for(int i=0;i<size;i++){

System.out.print(ar[i]+" , ");

}

System.out.println();

System.out.println("Bubble sort");

bubbleSort(ar);

for(int i=0;i<size;i++){

System.out.print(ar[i]+" , ");

}

System.out.println();

System.out.println("selection sort");

ar=getRandomNumberArray(size);

selSort(ar);

for(int i=0;i<size;i++){

System.out.print(ar[i]+" , ");

}

}

}

output

Normal array

95 , 51 , 74 , 81 , 31 , 69 , 92 , 38 , 32 , 37 , 19 , 75 , 3 , 79 , 99 , 24 , 3 , 74 ,

Bubble sort

3 , 3 , 19 , 24 , 31 , 32 , 37 , 38 , 51 , 69 , 74 , 74 , 75 , 79 , 81 , 92 , 95 , 99 ,

selection sort

3 , 6 , 7 , 21 , 24 , 30 , 41 , 43 , 49 , 51 , 52 , 63 , 71 , 73 , 81 , 89 , 93 , 98 ,

selection sort flowchart

Bubble Sort flowchar