Searching and Sorting

searching and sorting:
searching: linear and binary. Binary Search is generally more efficient than Linear
Search, especially for large datasets. Linear Search has a time complexity of O(n),
while Binary Search has a time complexity of O(log n). Binary Search requires
sorted data, whereas Linear Search does not.
Linear:
public static int liner(int arr[], int x)
{
for (int i = 0; i < arr.length; i++) {
if (arr[i] == x)
return i;
}
return -1;
}
binary code:
int binarySearch(int arr[], int x)
{
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
recursively:
int binarySearch(int arr[], int low, int high, int x)

{
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);
return binarySearch(arr, mid + 1, high, x);
}
return -1;
}
-----------------------------------------------------------------------------------
---------------------
sorting: The time complexity of Bubble sort is O(n) in the best case and O(n2) in
the worst case. The time complexity of Selection sort is O(n2) in both best and
worst cases. but selection sort is more efficient as selection sort performs
minimum number of swaps to sort the array. Bubble sort performs maximum number of
swaps to sort the array. so selection is faster but less stable.
Here's a brief explanation of each sorting algorithm:
1. **Selection Sort**:
- **Concept**: Repeatedly finds the smallest element from the unsorted portion
and swaps it with the first unsorted element.
- **Performance**: \(O(n^2)\) time complexity; simple but inefficient for large
datasets.
2. **Bubble Sort**:
- **Concept**: Repeatedly steps through the list, compares adjacent elements,
and swaps them if they're in the wrong order, "bubbling" the largest element to the
end.
- **Performance**: \(O(n^2)\) time complexity; inefficient for large datasets,
but easy to implement.
3. **Insertion Sort**:
- **Concept**: Builds a sorted portion of the list by repeatedly taking the next
element and inserting it into its correct position.
- **Performance**: \(O(n^2)\) time complexity; efficient for small datasets or
nearly sorted data.
4. **Merge Sort**:
- **Concept**: Divides the list into halves, recursively sorts them, and then
merges the sorted halves back together.
- **Performance**: \(O(nlog n)\) time complexity; efficient and stable, good for
large datasets.
5. **Quick Sort**:
- **Concept**: Selects a "pivot" element, partitions the array into elements
less than and greater than the pivot, and recursively sorts the partitions.
- **Performance**: Average \(O(nlog n)\) time complexity; efficient but can
degrade to \(O(n^2)\) in the worst case, though this can be mitigated with good
pivot selection.
-----------------------------------------------------------
selection sort:
void sort(int arr[])

{
int n = arr.length;
for (int i = 0; i < n-1; i++)
{
int min_idx = i;
for (int j = i+1; j < n; j++)
{if (arr[j] < arr[min_idx])
{min_idx = j;}}
int temp = arr[min_idx];

arr[min_idx] = arr[i];
arr[i] = temp;
}
}
---------------------------------------------------------
bubble sort
static void bubbleSort(int arr[], int n)

{
int i, j, temp;
boolean swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (swapped == false)
break;
}
}
-----------------------------------------------------
insertion: best O(n) and worst O(n2)
void sort(int arr[])

{
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
------------------------------------------------------------
merge sort: best and worst: O(nlogn)
static void merge(int arr[], int l, int m, int r)

{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays

int L[] = new int[n1];
int R[] = new int[n2];
// Copy data to temp arrays

for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
// Merge the temp arrays
// Initial indices of first and second subarrays

int i = 0, j = 0;
// Initial index of merged subarray array

int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements of L[] if any

while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[] if any

while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using

// merge()
static void sort(int arr[], int l, int r)
{
if (l < r) {
// Find the middle point

int m = l + (r - l) / 2;
// Sort first and second halves

sort(arr, l, m);
sort(arr, m + 1, r);
// Merge the sorted halves

merge(arr, l, m, r);
}
}
------------------------------------------------------------------
quick sort: worst O(n2) and best O(nlogn)
static void swap(int[] arr, int i, int j)

{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// This function takes last element as pivot,

// places the pivot element at its correct position
// in sorted array, and places all smaller to left
// of pivot and all greater elements to right of pivot
static int partition(int[] arr, int low, int high)
{
// Choosing the pivot
int pivot = arr[high];
// Index of smaller element and indicates
// the right position of pivot found so far
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot

if (arr[j] < pivot) {
// Increment index of smaller element

i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
// The main function that implements QuickSort

// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
static void quickSort(int[] arr, int low, int high)
{
if (low < high) {
// pi is partitioning index, arr[p]

// is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before

// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static void main(String[] args)

{
int[] arr = { 10, 7, 8, 9, 1, 5 };
int N = arr.length;
// Function call
quickSort(arr, 0, N - 1);
System.out.println("Sorted array:");
printArr(arr);
}
-------------------------------------------------------------------------
time complexity:
https://www.youtube.com/watch?v=9TlHvipP5yA
https://www.youtube.com/watch?v=5v-tKX2uRAk
1<logn<root n<n<nlogn<n2<n3...2^n<3^n...<n^n
for (int i = 2; i < n; i = pow(i, 2)) {

// Loop body
}
complexity: log(logn)
--------------------------------------------------------------------
time complexity of sorting algorithms:
Quick Sort:
Average-Case Time Complexity: O(n log n)
Worst-Case Time Complexity: O(n^2) (though this is rare with good pivot selection)
Performance: Typically the fastest in practice for large datasets, especially with
a good pivot selection strategy.
Merge Sort:
Average-Case Time Complexity: O(n log n)
Worst-Case Time Complexity: O(n log n)
Performance: Very reliable and consistent; often preferred for large datasets and
in applications requiring stable sorting.
Insertion Sort:
Average-Case Time Complexity: O(n^2)
Best-Case Time Complexity: O(n) (when the array is nearly sorted)
Performance: Fast for small or nearly sorted datasets, but not efficient for large
datasets.
Selection Sort:
Worst-Case Time Complexity: O(n^2)
Performance: Simple to implement but generally slower than other algorithms on
large datasets.
Bubble Sort:
Worst-Case Time Complexity: O(n^2)
Performance: Typically the slowest of the five, mainly used for educational
purposes or small datasets.
Summary:
Quick Sort is generally the fastest for large datasets.
Merge Sort is very efficient and reliable, especially when stable sorting is
required.
Insertion Sort can be the fastest for small or nearly sorted datasets.
Selection Sort and Bubble Sort are slower and generally not preferred for large
datasets.
-----------------------------------------------------------------------------------
----------------------------------
time complexity of searching algorithms:
linear: best- 1, avg and worst- n, space-1

binary best- 1, avg and worst- logn, space-1
--------------------------------------------------------------

Searching and Sorting

Uploaded by

Copyright:

Available Formats

Searching and Sorting

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Searching and Sorting

Uploaded by

Copyright:

Available Formats

searching and sorting:

int binarySearch(int arr[], int low, int high, int x)

Here's a brief explanation of each sorting algorithm:

void sort(int arr[])

int temp = arr[min_idx];

static void bubbleSort(int arr[], int n)

void sort(int arr[])

/* Move elements of arr[0..i-1], that are

static void merge(int arr[], int l, int m, int r)

// Create temp arrays

// Copy data to temp arrays

// Merge the temp arrays

// Initial indices of first and second subarrays

// Initial index of merged subarray array

// Copy remaining elements of L[] if any

// Copy remaining elements of R[] if any

// Main function that sorts arr[l..r] using

// Find the middle point

// Sort first and second halves

// Merge the sorted halves

static void swap(int[] arr, int i, int j)

// This function takes last element as pivot,

for (int j = low; j <= high - 1; j++) {

// If current element is smaller than the pivot

// Increment index of smaller element

// The main function that implements QuickSort

// pi is partitioning index, arr[p]

// Separately sort elements before

public static void main(String[] args)

for (int i = 2; i < n; i = pow(i, 2)) {

linear: best- 1, avg and worst- n, space-1

You might also like