CSharpArraySorting.md - brainchildservices/curriculum GitHub Wiki

Slide 1

Time Complexity and Sorting Algorithms:

Simple Exercise to be completed before learning Sorting Algorithms:

  • Q1: Take the size of array as input from user. Prompt user to enter elements to the array. Prompt user to enter any number. Create a program that checks if the number input by the user is present in the array and at which index.
    Test Data:
    Enter the size of array: 4
    Enter elements to array:
    1
    14
    15
    17

Slide 1 Downwards

Enter the element to be searched: 17
Expected Output:
Found 17 at index 3
Enter the size of array: 3
Enter elements to array:
1
13
10
Enter the element to be searched: 17
Expected Output:
17 not found in the array

Slide 2

  • Q2: Take the size of array as input from user. Prompt user to enter elements to the array. Prompt user to enter two index numbers. Write a program that the numbers at the index position provided by the user: Print the array with swapped numbers
    Test Data:
    Enter the size of array: 4
    Enter elements to array:
    1
    14
    15
    17

Slide 2 Downwards

Enter the index to be swapped:
1
3
Expected Output:
Array after swapping is
1 17 15 14

Enter the size of array: 6
Enter elements to array:
1
13
10
6
8
78
Enter the index to be swapped:
0
3
Expected Output:
Array after swapping is
6 13 10 1 8 78

Slide 3

  • Q3.1: Take the size of array as input from user. Prompt user to enter elements to the array. Write a program to print the largest number in the array
    Test Data:
    Enter the size of array: 4
    Enter elements to array:
    1
    14
    15
    17
    Expected Output:
    Largest number is: 17

Slide 4

  • Q3.2: Take the size of array as input from user. Prompt user to enter elements to the array. Write a program to print the smallest number in the array Test Data:
    Enter the size of array: 4
    Enter elements to array:
    1
    14
    -15
    17
    Expected Output:
    Smallest number is: -15

Slide 5

  • Q4: Take the size of array as input from user. Prompt user to enter elements to the array. Write a program to print the second largest number in the array without completely sorting the array.
    Test Data:
    Enter the size of array: 4
    Enter elements to array:
    1
    14
    -15
    17
    Expected Output:
    2nd largest number is: 14

Slide 6

  • Q5: Take the size of array as input from the user. Prompt user to enter elements to the array. Write a program to reverse the array(without using another array) and print the array
    Test Data:
    Enter the size of array: 4
    Enter elements to array:
    1
    14
    -15
    17
    Expected Output:
    The reversed array is : 17 -15 14 1

Slide 7

Time Complexity

Consider the example of finding the sum of first N Natural numbers. Case1: https://dotnetfiddle.net/zwKKen Using a for loop and adding each term to the sum.
But if we put one more zero, dotn't fiddle can no longer handle it as Execute time goes over 10 seconds.

Case2: https://dotnetfiddle.net/R82no9
Here we have used the arithmetic expression formula to calculate the sum of N terms. Since there is no for loop involved, the execution time is more fast and we can find the answer for larger and larger numbers.

The purpose of programming is not just to write some code, but to write code that has good performance and efficiency.
Finding out the time complexity of your code can help you develop better programs that run faster.

Slide 8

How to calculate the time complexity of any algorithm or program?
The most common metric is using Big O notation.

  • Big O notation cares about the worst-case scenario. E.g., when you want to sort and elements in the array are in reverse order for some sorting algorithms or the loop has to run all the iterations to complete the sorting.
  • It helps us to find the amount of work the CPU has to do (time complexity) as the input size grows (towards infinity).
  • Big O = Big Order function. Drop constants and lower order terms. E.g. O(3*n^2 + 10n + 10) becomes O(n^2).

image

Slide 9

Slide 10

Sorting Algorithms:

Sorting algorithms are a set of instructions that take an array or list as an input and arrange the items into a particular order.

Some of the most common sorting algorithms we are going to learn are :

Slide 11

  • Selection Sort : Smallest number is found and saved to the start of the index on first iteration. In the next iteration, the next smallest number is found and is saved to the second index and so on.
    Time Complexity: O(n2) https://www.youtube.com/watch?v=GUDLRan2DWM&t=321s
    Method1 : Finding the index of the smallest number and swapping the numbers after the inner for loop iteration completes
    https://dotnetfiddle.net/2enz3R

Method2: Swapping the numbers between start of the unsorted array section and the number as soon as a smaller number is found https://dotnetfiddle.net/D6SWh9

Slide 12

Slide 13

Slide 14

Slide 15

⚠️ **GitHub.com Fallback** ⚠️