This is a java program that runs on the Eclipse. Java Programming 2-6: Sorting a

Question

This is a java program that runs on the Eclipse.

Java Programming 2-6: Sorting and Searching Practice Activities Lesson objectives: Recognize the sort order of primitive types and objects Trace and write code to perform a simple Bubble Sort of integers Trace and write code to perform a Selection Sort of integers Trace and write code to perform a Binary Search of integers Compare and contrast search and sort algorithms Analyze the Big-O for various sort algorithms Vocabulary Identify the vocabulary word for each definition below. Also called a linear search, an algorithm that searches through an array until a value is found. The array does not need to be sorted An algorithm that finds the minimum value in an array and swaps that value with the first number in the array. The next smallest value is swapped with the second number in the array. The process is repeated until the array is sorted. An algorithm that checks the value of the first two elements, then swaps them if necessary so that the larger of the two is the second number. Next, the second and third numbers are compared. The larger of those two are swapped, if necessary so that the larger of the two is the second number. The process continues until the largest number in the array is the last number in the array. Then the process is repeated until the array is sorted. A search algorithm that works with sorted data. The array is divided in half, searched in the correct half repeatedly, until the item is found An algorithm that divides an array in half repeatedly until all data is isolated. Then the isolated data is "merged" back together in correct order. The ASCII sort order for data. Try It/Solve It 1. Create an array of Strings that stores all the names of the students in your class. Sort it using one of the algorithms covered in this lesson. Do a binary search for your name in the sorted list and find out what index your name is at in the list of your classmates

Explanation / Answer

Vocabulary:

1)Sequential Search

2)Selection Sort

3)Bubble Sort

4)Binary Search

5)Merge Sort

6)Insertion Sort

Try it/solve it

1)

import java.util.Scanner;

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
* @author Surya
*/
public class strings {
  
  
//method to sort array of student names ....using selection sort...technique..
static void selectionSort(String s[])
{
  
int n=s.length;
  
int min;//to store min index ..every time..
  
int i,j;//to traverse the array
  
String temp;
for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
  
if(s[j].compareTo(s[min])<0)
min=j;
}
//swapping
temp=s[i];
s[i]=s[min];
s[min]=temp;
  
  
}
  
  
  
}
  
  
//method to print the array...
  
static void print_array(String s[])
{
int n=s.length;
int i;
System.out.println("-----------------------------------");
for(i=0;i<n;i++)
{
System.out.print(s[i]+" ");
}
System.out.println(" -----------------------------------");
}
  
  
//search method, to search string in a given sorted array...using binary search technique
static int binarysearch(String s[],String search)
{
  
int n=s.length;
  
int low = 0,high=n,mid;
mid = (low+high)/2;
  
  
  
while(low<=high)
{
if(s[mid].equals(search))
{
//if found returning index
  
return mid;
}
else if(s[mid].compareTo(search)>0)
{
  
high=mid-1;
}
else
{
  
low = mid+1;
}
  
mid = (low+high)/2;
  
  
}
  
  
  
  
  
  
  
  
//if not found
return -1;
  
}
  
  
public static void main(String argv[])
{
  
  
//creating an array...to store te names...
  
String students[] = {"surya","vamsi","rk","abhi","mohan","ashok","phani"};

//printing array
//before sorting
  
System.out.println("Before sorting:");
print_array(students);
  
  
//calling sorting function...
  
selectionSort(students);
  
  
  
//printing array
//after sorting
  
System.out.println("after sorting:");
print_array(students);
  
  
  
Scanner sc = new Scanner(System.in);
  
String search;
  
//taking input from user...
System.out.println("Enter name to search:");
search = sc.next();
  
//calling binary search function
  
  
int m = binarysearch(students,search);
if(m!=-1)
{
System.out.println("Found at index :"+m);
}
else
{
System.out.println("Not found ");
  
}
  
  
}
  
}

output:-

run:
Before sorting:
-----------------------------------
surya vamsi rk abhi mohan ashok phani
-----------------------------------
after sorting:
-----------------------------------
abhi ashok mohan phani rk surya vamsi
-----------------------------------
Enter name to search:
mohan
Found at index :2
BUILD SUCCESSFUL (total time: 5 seconds)

2)

Selection sort:

Worst : O(n^2)

Average : O(n^2)

Best : O(n^2)

Notes:

in selection sort, we have to find minimum n times. to find minimum it takes O(n), so totally O(n^2)..IN ALL the cases(best,average,worst)

Bubble Sort:

Worst: O(n^2)

Average :O(n^2)

Best : O(n^2)

Notes:

In Bubble sort: we have to all compare adjacent items..in each iteration, for this we need two loops, hence the comlexity would be.. O(n^2)

Merge Sort:

Worst: O(nLog n)

Average : O(nLog n)

Best :O(nLog n)

Notes:

In megre sort : it divides arrayy into half every time (it takes O(log n)), and then it merges in sorted order.. total O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.