I wrote the selection sort in C

Selection sort (C language)

What is selection sort?

-In-place integer algorithm. Selection sort is suitable for small files. -Repeat finding the minimum value in ascending order (smallest order) and the maximum value in descending order (largest order). -N-1 exchanges are performed to align n elements. N-1 comparisons on pass 1 N-2 comparisons in pass 2 ... (because the data to be compared is reduced by 1) Therefore, (n-1) + (n-2) + ... + 1 = n (n-1) / 2 comparisons are performed.

advantage

・ Easy to understand · In-place sort (no additional storage required) ・ Faster than bubble sort

Disadvantage

・ Deterioration of computational complexity due to scale: O (n²)

Overall flow

  1. Find the minimum (maximum) value in the list.
  2. Exchange for the value at the current position.
  3. Repeat this process for all elements until the entire array is aligned.

In implementation

Implement in C language. Display English and math scores in descending order (largest order). Use selection sort to sort the data.

code

selection_sort.c


#include <stdio.h>
#define NMAX 1000
int main(){
    int eigo[NMAX], math[NMAX], gokei[NMAX], n, max, work;
    printf("data="); scanf("%d", &n);
    for (int i = 0; i <n ; ++i) {
        printf("[%3dbanme]=", i); scanf("%d %d", &eigo[i], &math[i]);
        gokei[i]=eigo[i]+math[i];
    }
    for (int i = 0; i <n-1 ; ++i) {
        max=i;
        for (int j = i+1; j <n ; ++j) {
            if (gokei[j]>gokei[max]) max=j;
        }
        if(i!=max) {
            work=eigo[i];eigo[i]=eigo[max];eigo[max]=work;
            work=math[i];math[i]=math[max];math[max]=work;
            work=gokei[i];gokei[i]=gokei[max];gokei[max]=work;
        }
    }
    printf("*** RESULTS ***\n");
    printf("RANK   ENGLISH   MATH   TOTAL\n");
    for (int i = 0; i <n ; ++i) {
        printf("%4d%6d%6d%6d\n", i, eigo[i], math[i], gokei[i]);
    }
}

Computational complexity of sorting

type Computational complexity
Worst case complexity O(n²)
Best time complexity O(n)
Average complexity O(n²)
Worst spatiotemporal complexity O(1)Auxiliary area

I may add it if something happens again

Recommended Posts

I wrote the selection sort in C
I wrote the queue in Python
I wrote the stack in Python
I wrote the sliding wing in creation.
I wrote the hexagonal architecture in go language
I tried to implement selection sort in python
I wrote python in Japanese
I wrote the basic operation of Seaborn in Jupyter Lab
I tried to illustrate the time and time in C language
I wrote it in Go to understand the SOLID principle
I wrote the basic operation of Numpy in Jupyter Lab.
Implemented the algorithm of "Algorithm Picture Book" in Python3 (selection sort)
I wrote a script that splits the image in two
sort warning in the pd.concat function
I participated in the ISUCON10 qualifying!
I wrote Fizz Buzz in Python
I wrote Gray Scale in Pytorch
Selection Sort
I wrote the code to write the code of Brainf * ck in python
Implement part of the process in C ++
I saved the scraped data in CSV!
I can't get the element in Selenium!
I wrote the code for Gibbs sampling
[Python beginner] I collected the articles I wrote
I wrote Project Euler 1 in one liner.
[C language] I want to generate random numbers in the specified range
I want to sort a list in the order of other lists
AOJ Sort I-
How to use the C library in Python
[Python] Sort the list of pathlib.Path in natural sort
A memo that I wrote a quicksort in Python
[Fundamental Information Technology Engineer Examination] I wrote the algorithm of Euclidean algorithm in Python.
I tried simulating the "birthday paradox" in Python
I tried the least squares method in Python
I wrote a class in Python3 and Java
I wrote matplotlib
I wrote "Introduction to Effect Verification" in Python
Note that I understand the least squares algorithm. And I wrote it in Python.
I can't enter characters in the text area! ?? !! ?? !! !! ??
I wrote a PyPI module that extends the parameter style in Python's sqlite3 module
I wrote a design pattern in kotlin Prototype
I implemented the inverse gamma function in python
I tried adding a Python3 module in C
I wrote a Japanese parser in Japanese using pyparsing.
I checked the calendar deleted in Qiita Advent Calendar 2016
I implemented Human In The Loop ― Part ① Dashboard ―
I want to display the progress in Python!
I tried to graph the packages installed in Python
Sort in Python. Next, let's think about the algorithm.
I wrote a design pattern in kotlin Factory edition
I tried using google test and CMake in C
I wrote a design pattern in kotlin Builder edition
I wrote a design pattern in kotlin Singleton edition
I wrote a design pattern in kotlin Adapter edition
I wrote a design pattern in kotlin, Iterator edition
I want to write in Python! (3) Utilize the mock
I felt that I ported the Python code to C ++ 98.
[Note] I can't call the installed module in jupyter
I wrote a design pattern in kotlin Template edition
What I learned by participating in the ISUCON10 qualifying
I want to use the R dataset in python