Related questions

Counting sort in C apparently works but binarysearch doesn't

2017-06-17 18:52 J.Ober imported from Stackoverflow

I am looking for help regarding the implementation of a counting sort function in the CS50 Course in week 3.

An int Array has to be sorted. I tested various unsorted arrays and my counting sort function seems to sort the array just correctly, yet my search functions won't work on the sorted array after. Could someone give me a hint? 

void countsort( int array[], int size) {

    int count=0;
    int zahl=0;
    int max=65536;
    int countarr [max];
    int finalarr [size];

    memset (countarr, 0, sizeof(countarr));

    for(int i=0;i<size;i++) {
        zahl=array[i];
        countarr[zahl]++;
    }

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

        while(countarr[i]>0) {
            finalarr[count]=i;
            countarr[i]--;
            count++;

        }
    }
    array=finalarr;

    for(int i=0;i<size;i++){
        printf(" %i ",array[i]);
    }
}

This is my search algorithm used after the array is sorted, it works with sort algorithms from other people.

bool binarysearch(int value, int values[], int n){

    int start=0,
        end=n,
        mid=0,
        midpos=0;

    while(end>0) {

        midpos=(start+end)/2; 

        mid=values[midpos];

        if(mid==value) return true;

        if(mid<value) start=++midpos;

        if(mid>value) end=--midpos;

    }
    return false;
}

1 answer

  • answered 2017-06-17 18:52 Gassa

    1. In binarysearch, the loop condition while(end>0) is wrong. If we search for a value which is greater than at least one of the elements of the array, end will never be zero. Try changing it to while(end>=start), which literally means that the considered interval is non-empty.

    2. In countsort, the line array=finalarr; does not copy the whole array. Instead, the local variable array becomes a pointer to finalarr. The contents of the original array remain unchanged, and the sorted array is gone when you exit the function. This explains why your binary search works (better) with other sort functions.
      Try changing finalarr[count]=i; to array[count]=i; and get rid of finalarr completely, putting the values into array right away. Alternatively, you can use memmove instead of that line.

See also questions close to this topic

  • C Segmentation fault Error reading characters of string

    I'm trying to make a sudoku solver. I get my input data from argumets ( 9 lines with 9 characters ). I did the backtrack part and the verify of rows,columns and each square but i get Segmentation Fault after I assign the characters to the new matrix.

    char    **ft_matrix(char **argv)
{
    char    **matrix;
    int     i;
    int     j;

    i = 1;
    matrix = (char**)malloc(sizeof(char*) * 9);
    while (i < 10)
    {
        matrix[i] = (char*)malloc(sizeof(char) * 9);
        i++;
    }
    i = 1;
    while (i < 10)
    {
        j = 0;
        while (j < 9)
        {
            matrix[i][j] = argv[i][j];
            j++;
        }
        printf("\n");
        i++;
    }
    return (matrix);
}

int     main(int argc, char **argv)
{ 
    char **matrix2;
    if(argc == 10)
    {
        matrix2 = ft_matrix(argv);
        //ft_solve(matrix);
    }
    return (0);
}
  • Why below code wont generate a random string on multiple runs?

    Program uses rand() function to generate random index. But it always produces same string no matter what! Why won't this work?

    void rand_string()
{
    int a[10];
    int i;
    char b[] = "qwertyuiopasdfghjklzxcvbnm1234567890QWERTYUIOPASDFGHJKLZXCVBNM";
    printf("%d", sizeof(b) / sizeof(b[0]));

    for(i = 0; i < 10; i++)
    {
        int gen_rand = rand() % 63; 
        a[i] = b[gen_rand];
    }

    for(i = 0; i < 10; i++)
        printf("%c", a[i]);
}
  • An algorithm to compute rectangles (quads) from a set of joint center-lines?

    For example we have center-lines of quad shapes and the thickness of these quads, and we need to compute the coordinates of the enclosing rectangle/quad. It is preferable that these joint lines be a 90 degrees of each other, yet it could occur that three or more center-lines could meet at a certain point. Thus, sides of a quad shape might overlap if they are right angles in the quad itself, and a solution would be to cut them at a computed angle.

    The undesired and desired outcome is shown on the second and third rows respectively for the two examples I am demonstrating on the first row.

    Is there an algorithm (preferably code) that could help get the coordinates of the final quad shapes? Supporting Image https://i.stack.imgur.com/9BVjC.jpg

  • Algorithm to find the days between two dates

    I was working with a school question to figure out the algorithm to find the days between two given dates which would then be implemented in Java.

    The algorithm of interest was found here: http://www.sunshine2k.de/articles/coding/datediffindays/calcdiffofdatesindates.html (Point 4)

    It was one of the more efficient algorithms because it would have the least conditions to consider during the implementation. I understand how it works in this context, but I couldn't quite wrap my mind around the use of an origin/reference point anywhere else because it seems that a simple subtraction would get most jobs done.

    Eg. To find the difference between 9 and 5, I could just do 9-5 instead of

    ref = 1

    difference = (9-ref) - (5-ref)

    Question: Why does using this reference/origin point work in this situation? What other situations can I consider using this reference/origin point to solve problems?

  • Algorithm to find optimal payment-to-items assignment

    I'm developing a system to distribute payments over items. The goal is to find an optimal payment-to-items assignment, the main rules of distribution are following:

    • Items can be partially payed one or more payment types
    • Some items cannot be payed with some payment types
    • Payments are done one by one, the distribution of payments over items should be (re-)calculated after each partial payment

    The simple scenario. The cart contains items:

    • Item1 with the price of $3 can be payed with PaymentType1 and PaymentType2
    • Item2 with the price of $1 can be payed with PaymentType1 only

    and the payments:

    • PaymentType1 for $2
    • PaymentType2 for $2

    As a result the optimal assignment of payments over items:

    • Item1 payed with PaymentType1 for $1 and with PaymentType2 with $2
    • Item2 payed with PaymentType1 for $1

    I was thinking about using Hungarian algorithm, but it has a restriction that one worker can do one job, meaning item cannot be payed with several payments.

  • How to find all solutions satisfying maximum bipartite matching?

    Maximum bipartite matching is a sort of max flow problem that can be perfectly solved by a lot of algorithms. However, the algorithms I have found so far seem to only return the maximum number, and what I am interested in is all the solutions that reach the maximum number.

    Alternatively speaking, if the the maximum bipartite matching is 5, then I want to get all situations that have 5 matchings. Any algorithms exist?

    Thanks!

  • Sorting with Java 8 by Field given as Input

    I have a REST endpoint and I want the UI to pass the field name that they want to sort their result by. 'id', 'name', etc. I came up with below, but was really trying to use Reflection / Generics so this could be expanded to encompass every object in my project.

    I feel like this solution isn't easily maintainable if I want to have the same functionality for 100 different classes.

    public static void sort(List<MovieDTO> collection, String field){

        if(collection == null || collection.size() < 1 || field == null || field.isEmpty()){
            return;
        }
        switch(field.trim().toLowerCase()){
        case "id": 
            collection.sort(Comparator.comparing(MovieDTO::getId));
            break;
        case "name": 
            collection.sort(Comparator.comparing(MovieDTO::getName));
            break;
        case "year": 
            collection.sort(Comparator.comparing(MovieDTO::getYear));
            break;
        case "rating": 
            collection.sort(Comparator.comparing(MovieDTO::getRating));
            break;
        default: 
            collection.sort(Comparator.comparing(MovieDTO::getId));
            break;
        }
    }

    Any ideas on how I could implement this better so that it can be expanded to work for an enterprise application with little maintenance?

  • Why does compareFunction has to consider negative?

    Array.prototype.sort()

    In compareFunction(a, b), only when we need to exchange a and b's position, we return a positive value.

    If negative if-statement in compareFunction is omitted, the Array.prototype.sort() still works, so why should developers write if-statement which returns a negative value?

    var list = [4, 5, 3, 5, 6, 9, 1, 4, 2];
list = list.sort(function(a, b) {
  if (a > b) {
    return 1;
  }
});
console.log(list); // correct result

  • I am using ArrayAdapter with a List in a GridView. How can I configure to sort based on object variables from my ArrayAdapter?

    I am displaying an ArrayAdapter of objects MyBears in a GridView and I want to configure the order in which my objects from my ArrayAdapter are sorted in the GridView. I want to order the bears e.g. new myBear(27, "Hi", 48) based on the last parameter (in this case 48 - method is myBear.getSize()). How can I do this and where do I need to put this code. I tried to implement what I saw in other posts but none of them work.

    Here is my xml where the grid appears:

    <LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_height="match_parent"
    android:layout_width="match_parent"
    android:background="@drawable/background_Bears"
    android:orientation="vertical”>
    <GridView
        android:id="@+id/my_Bears_in_my_collection_grid_view"
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:divider="@android:color/transparent"
        android:gravity="center"
        android:numColumns="4"
        android:visibility="visible"
        tools:griditem="@layout/one_my_Bear_in_my_collection_display" />
</LinearLayout>

    Here is where I connect the array adapter with the grid.

    public class MyCollectionFragment extends Fragment {


    private GridView mMyBearGridView;

    @Override
    public View onCreateView (LayoutInflater inflater, @Nullable final ViewGroup container, @Nullable Bundle savedInstanceState){
        View v = inflater.inflate(R.layout.my_collection,container,false);

        myBearsList = new ArrayList<>();
        mMyBearsAdapter = new MyBearsMyCollectionAdapter(this, R.layout.one_my_Bear_in_my_collection_display, myBearsList);
        mMyBearsAdapter.add(new myBear(27, "Hi", 48));
        mMyBearsAdapter.add(new myBear(4, "Hi", 87));
        mMyBearsAdapter.add(new myBear(6, "Hi", 39));
        mMyBearsAdapter.add(new myBear(8, "Hallo", 90));
        mMyBearsAdapter.add(new myBear(0, "Hi", 28));
        mMyBearsAdapter.add(new myBear(8, "Bye", 54));
        //the grid view from this fragment
        mMyBearGridView = (GridView) v.findViewById(R.id.my_Bears_in_my_collection_grid_view);
        mMyBearGridView.setAdapter(mMyBearsAdapter);

        return v;
    }

}

    Here is my ArrayAdapter:

    public class MyBearsMyCollectionAdapter extends ArrayAdapter<MyBear> {
    private Context context;

    public MyBearsMyCollectionAdapter(Context context, int resource, List<MyBear> objects) {
        super(context, resource, objects);
        this.context = context;
    }

    @Override
    public View getView(int position, View convertView, ViewGroup parent) {
        if (convertView == null) {
            convertView = ((Activity) getContext()).getLayoutInflater().inflate(R.layout.one_my_Bear_in_my_collection_display, parent, false);
        }

        LinearLayout myBearsMyCollectionLinearLayout = (LinearLayout) convertView.findViewById(R.id.my_Bear_linear_layout);
        ImageView myBearImage = (ImageView) convertView.findViewById(R.id.my_Bear_image);

        final MyBear myBear = getItem(position);

        boolean isPhoto = myBear.getBearImageUrl() != null;
        if (isPhoto) {
            Glide.with(myBearImage.getContext())
                    .load(myBear.getBearImageUrl())
                    .into(myBearImage);
        }

        myBearsMyCollectionLinearLayout.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View view) {
                BearPopup BearPopup = BearPopup.newInstance(myBear);
                FragmentManager manager = ((MainActivity) context).getSupportFragmentManager();
                BearPopup.show(manager, "BearPopup");
            }
        });
        return convertView;
    }

}
  • CS50 PSET3 Game of Fifteen for loop stops

    So I am stuck at initializing the board. my for loop is doing what it should but it stops when it is not actually done. The board I initialize is made of the dimensions >d*d and should start left to right, top to bottom from >d*d-1 counting down and leave the last one empty. I'm not far enough to let the last one empty, my problem is it stops whenever it reaches the number 9, it doesn't matter which size I run it with, it will always stop when it reaches the number 9. 

    void init(void)
{
    int down=1;
    for(int i=0;i<d;i++)
    {
        for(int j=0;j<d;j++)
        {
            board[i][j]=(d*d)-down;
            down++;
            printf("Zahl:%i, i=%i, j=%i\n", board[i][j], i, j);
        }
    }
}

    Zahl:15, i=0, j=0
    Zahl:14, i=0, j=1
    Zahl:13, i=0, j=2
    Zahl:12, i=0, j=3
    Zahl:11, i=1, j=0
    Zahl:10, i=1, j=1
    Zahl:9, i=1, j=2

    This is when I give it the size of 4x4. I'm using printf to find where it goes wrong. I don't understand why it stops when i=1 and j=2 while I declared it to only stop when it would reach 4. If I choose 5x5 it will still stop when it reaches the number 9. Has this something to do with the defined dimensions of the board?

    #define DIM_MIN 3
#define DIM_MAX 9

    entire code Max example

    Exact instructions

    Edited in all relevant informations

  • Solving Error in `./recover': free(): invalid next size (normal): 0x0000000001ddd270 *** Aborted in c

    Code must read 512 bytes at a time from a file that has raw JPEGs in order to retrieve them. When a JPEG is found, all the following blocks of 512 bytes are stored in a a file until a new JPEG is found, once a new JPEG is found, the file img is closed and then opened as new to store a new image. The code runs fine if I comment or erase the fclose(img); line, othwerwise it shows the error above.

    Here's the code

    #include <stdio.h>
#include <cs50.h>
#include <stdlib.h>


int main (int argc, char *argv[]){

if(argc != 2){

    fprintf(stderr, "Usage: ./recovery image\n");
    return 1;

}

FILE *card = fopen(argv[1], "r");

if (card == NULL){

    fprintf(stderr, "Cannot open image\n");
    return 2;

}

FILE *buffer1 = malloc(sizeof(card));

int n = 0;
int picsNum = 0;

while(fread(buffer1, 512, 1, card)){

    n ++;

}

//printf("%i", n);

bool foundJPEG = false;
int j = 0;
bool fstJPEG = false;
FILE *img = NULL;
int counter = 0;

fseek(card, 0, SEEK_SET);

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


    unsigned char fst;
    unsigned char snd;
    unsigned char thrd;
    unsigned char fth;
    unsigned char buffer2[508];

    fread(&fst, 1, 1, card);
    fread(&snd, 1, 1, card);
    fread(&thrd, 1, 1, card);
    fread(&fth, 1, 1, card);
    fread(buffer2, 508, 1, card);
    //printf("%i,%i,%i,%i,", fst, snd, thrd, fth);

    if(fst == 0xff && snd == 0xd8 && thrd == 0xff && (fth & 0xf0) == 0xe0){

        printf("Found\n");

        if(fstJPEG){

            fclose(img);

        }

        printf("%i,%i,%i,%i,", fst, snd, thrd, fth);
        foundJPEG = true;
        picsNum++;
        fstJPEG = true;

        char JPEG[8];
        sprintf(JPEG, "%03i.jpg", j);
        j++;
        img = fopen(JPEG, "w");

    } else {

        foundJPEG = false;

    }

    if(fstJPEG){

        fwrite(&fst, 1, 1, card);
        fwrite(&snd, 1, 1, card);
        fwrite(&thrd, 1, 1, card);
        fwrite(&fth, 1, 1, card);
        fwrite(buffer2, 508, 1, card);
        counter++;
        printf("%i,", counter);

    }

}    

fclose(card);    
printf("%i,\n", picsNum);

}
  • Suggestion box only displays , ,

    I am making a mashup website that involves a map, and a search textbox in javascript. So as the title says, no matter what is inputted into the search box, only 2 commas appear in the suggestion box and when the suggestion is clicked on, it turn the map gray and unusable. Whats the problem? This is my javascript file, the function where this is located is in the configure function

    // Google Map
var map;

// markers for map
var markers = [];

// info window
var info = new google.maps.InfoWindow();

// execute when the DOM is fully loaded
$(function() {

// styles for map
// https://developers.google.com/maps/documentation/javascript/styling
var styles = [

    // hide Google's labels
    {
        featureType: "all",
        elementType: "labels",
        stylers: [
            {visibility: "off"}
        ]
    },

    // hide roads
    {
        featureType: "road",
        elementType: "geometry",
        stylers: [
            {visibility: "off"}
        ]
    }

];

// options for map
// https://developers.google.com/maps/documentation/javascript/reference#MapOptions
var options = {
    center: {lat: 35.7640, lng: -78.7786}, // Cary, North Carolina
    disableDefaultUI: true,
    mapTypeId: google.maps.MapTypeId.ROADMAP,
    maxZoom: 14,
    panControl: true,
    styles: styles,
    zoom: 13,
    zoomControl: true
};

// get DOM node in which map will be instantiated
var canvas = $("#map-canvas").get(0);

// instantiate map
map = new google.maps.Map(canvas, options);

// configure UI once Google Map is idle (i.e., loaded)
google.maps.event.addListenerOnce(map, "idle", configure);

});

/**
 * Adds marker for place to map.
 */
function addMarker(place)
{
var url = "/search?q=" + place;
$.getJSON(url, function(data){
    var location = data.latitude + data.longitude;
    mark = new google.maps.marker(location, map);
    markers[0] = mark;
});

}

/**
 * Configures application.
 */
function configure()
{
// update UI after map has been dragged
google.maps.event.addListener(map, "dragend", function() {

    // if info window isn't open
    // http://stackoverflow.com/a/12410385
    if (!info.getMap || !info.getMap())
    {
        update();
    }
});

// update UI after zoom level changes
google.maps.event.addListener(map, "zoom_changed", function() {
    update();
});

// configure typeahead
$("#q").typeahead({
    highlight: false,
    minLength: 1
},
{
    display: function(suggestion) { return null; },
    limit: 10,
    source: search,
    templates: {
        suggestion: Handlebars.compile(
            "<div>" +
            "<p>{{ place_name }}, {{ admin_name1 }}, {{ postal_code }}</p>" +
            "</div>"
        )
    }
});

// re-center map after place is selected from drop-down
$("#q").on("typeahead:selected", function(eventObject, suggestion, name) {

    // set map's center
    map.setCenter({lat: parseFloat(suggestion.latitude), lng: parseFloat(suggestion.longitude)});

    // update UI
    update();
});

// hide info window when text box has focus
$("#q").focus(function(eventData) {
    info.close();
});

// re-enable ctrl- and right-clicking (and thus Inspect Element) on Google Map
// https://chrome.google.com/webstore/detail/allow-right-click/hompjdfbfmmmgflfjdlnkohcplmboaeo?hl=en
document.addEventListener("contextmenu", function(event) {
    event.returnValue = true; 
    event.stopPropagation && event.stopPropagation(); 
    event.cancelBubble && event.cancelBubble();
}, true);

// update UI
update();

// give focus to text box
$("#q").focus();
}

/**
 * Removes markers from map.
 */
function removeMarkers()
{
// TODO
}

/**
 * Searches database for typeahead's suggestions.
 */
function search(query, syncResults, asyncResults)
{
// get places matching query (asynchronously)
var parameters = {
    q: query
};
$.getJSON(Flask.url_for("search"), parameters)
.done(function(data, textStatus, jqXHR) {

    // call typeahead's callback with search results (i.e., places)
    asyncResults(data);
})
.fail(function(jqXHR, textStatus, errorThrown) {

    // log error to browser's console
    console.log(errorThrown.toString());

    // call typeahead's callback with no results
    asyncResults([]);
});
}

/**
 * Shows info window at marker with content.
 */
function showInfo(marker, content)
{
// start div
var div = "<div id='info'>";
if (typeof(content) == "undefined")
{
    // http://www.ajaxload.info/
    div += "<img alt='loading' src='/static/ajax-loader.gif'/>";
}
else
{
    div += content;
}

// end div
div += "</div>";

// set info window's content
info.setContent(div);

// open info window (if not already open)
info.open(map, marker);
}

/**
 * Updates UI's markers.
 */
function update() 
{
// get map's bounds
var bounds = map.getBounds();
var ne = bounds.getNorthEast();
var sw = bounds.getSouthWest();

// get places within bounds (asynchronously)
var parameters = {
    ne: ne.lat() + "," + ne.lng(),
    q: $("#q").val(),
    sw: sw.lat() + "," + sw.lng()
};
$.getJSON(Flask.url_for("update"), parameters)
.done(function(data, textStatus, jqXHR) {

   // remove old markers from map
   removeMarkers();

   // add new markers to map
   for (var i = 0; i < data.length; i++)
   {
       addMarker(data[i]);
   }
})
.fail(function(jqXHR, textStatus, errorThrown) {

    // log error to browser's console
    console.log(errorThrown.toString());
});
};
  • C++ Counting Sort Implementation not returning expected output?

    This is the implementation I came up with from Intro to Algorithms 3rd Edition by Thomas H. Cormen on page 195.

    #include <iostream>
#include <cstdlib>
#define length 10
#define rnds 10

using namespace std;

int rng[length];
int sorted[length];

int countingSort(int A[], int k){
    int C[k];
    for (int i = 0; i < k; i++){
        C[i] = 0;
    }
    for (int j = 1; j < length; j++){
        C[A[j]]++;
    }
    for (int i = 1; i < k; i++){
        C[i] += C[i-1];
    }
    for (int j = length; j >= 1; j--){
        sorted[C[A[j]]] = A[j];
        C[A[j]]--;
    }
    return 0;
}

int main(){
    for (int i=0; i<length; i++){
        rng[i]=rand()%rnds; //don't want random numbers to be too big, hard to read
        cout << rng[i] << endl;
    }
    cout << "Sorted" << endl;
    countingSort(rng, rnds);
    for (int i = 0; i < length; i++){
        cout << sorted[i] << endl;
    }
    return 0;
}

    The random numbers produced were:

    3
6
7
5
3
5
6
2
9
1

    The output was this:

    Sorted
0
1
2
3
5
5
6
6
7
9

    The number of threes is incorrect. There are 2 threes but only one appeared in the sorted array and an anomalous zero also appeared at the primary index.

    Why does this occur?

    The following is the pseudocode from the book:

    COUNTING-SORT(A,B,k)

    1 let C[ 0...k ] be a new array

    2 for i = 0 to k

    3 C[ i ] = 0

    4 for j = 1 to A.length

    5 C[A[ j ]] = C[A[ j ]] + 1

    6 // C[ i ] now contains the number of elements equal to i.

    7 for i = 1 to k

    8 C[ i ] = C[ i ] + C[ i - 1]

    9 // C[ i ] now contains the number of elements less than or equal to i.

    10 for j = A.length downto 1

    11 B[C[A[ j ]]] = A[ j ]

    12 C[A[ j ]] = C[A[ j ]] - 1

  • Counting sort segmentation fault in C

    Below is my attempt at a counting sort. I have diagrammed my logic, run through it verbally, and commented my code thoroughly. However, my code causes a segmentation fault. I understand a segmentation fault represents an illegal access to memory, so this must mean one of my index values is trying to access an index outside of an array's range. However, I can't figure out why this is happening.

    Fortunately, my debugger highlights the line below, which I've also noted in a comment, where the segmentation fault occurs. Nevertheless, I am entirely stumped. Would appreciate any help understanding the nature of this segmentation fault, thank you.

    void sort(int values[], int n)
{

    //create array of finite size (65536)
    int countArray[INT_MAX];

    //create array to eventually store sorted values
    int sortedValues[n];

    //loop through unsorted values to increment countArray index for each occurrence
    for(int i = 0; i < n; i++) {
        countArray[ values[i] ] += 1;
    }


    //starting index for sortedValues[]
    int sortedIndex = 0;

    //loop until we've reached the end of sortedValues[]
    while(sortedIndex < n) {

        //loop through each index value of countArray
        //j represents the value
        for(int j = 0; j < INT_MAX; j++) {

            //how many times does the index of countArray occur in values[]?
            int c = countArray[j];

            //only add index j as a value to sortedValues[] if it appears in values[]
            while(c > 0) {

                //append j to sortedValues[]
                //--SEGMENTATION FAULT OCCURS ON THE LINE BELOW--
                sortedValues[sortedIndex] = j;

                //decrease the count of countArray[j] once value appended to sortedValues[]
                c -= 1;

                //move to next index of sortedValues[]
                sortedIndex += 1;
            }
        } 
    }
    return;
}
  • How to counting sort two dimensional array

    Hi i have a problem with my code, i try sort array by counting sort (it must be stable sort), but my code doesn't work. I try implemented counting-sort from some wbesite, but it was in c# and I'm not sure s it done correctly. Can you tell me what is wrong with it?

    #include <stdio.h>
#include <iostream>

using namespace std;


void sort_with_show(int **a, int rozmiar, int polecenie)
{
    int y, d;
    for (int i = 0; i< rozmiar - 1; i++)
    {
        for (int j = 0; j < rozmiar - 1 - i; j++)
        {
            if (a[j + 1][0] < a[j][0])
            {
                y = a[j][0];
                a[j][0] = a[j + 1][0];
                a[j + 1][0] = y;
            }
        }
    }

    for (int i = 0; i < rozmiar; i++)
    {
    //cout << tablica[i].x << " " << tablica[i].y << "\n";
        if (polecenie == 0)
        {
            cout << a[i][0] << '\n';
        }
        else if (polecenie == 1)
        {
            cout << a[i][0] << "," << a[i][1] << "\n";
        }
    }
}

int main()
{


    int rozmiar = 0;
    int polecenie = 0;

    char t[20] = { '\0' };
    char *p, *q;

    int liczba = 0;
    int calaLiczba = 0;

    bool isY = false;
    cin >> rozmiar;

    int ** a  = new int *[rozmiar];
    for (int i = 0; i < rozmiar; i++)
        a[i] = new int[2];

    cin.ignore();

    int i = 0;
    while(i < rozmiar)
    {
        fgets(t, sizeof t, stdin);

        for (p = t, q = t + sizeof t; p < q; p++)
        {

            if (*p >= 48 && *p <= 57)
            {
                liczba = *p - 48;
                calaLiczba = calaLiczba * 10 + liczba;
            }

            if (*p == ' ')
            {
                a[i][0] = calaLiczba;
                isY = true;
                calaLiczba = 0;
                liczba = 0;
            }

            if (*p == '\n')
            {
                a[i][1] = calaLiczba;
                isY = false;
            }

        }

        for (int j = 0; j < 20; j++)
            t[j] = '\0';

        liczba = 0;
        calaLiczba = 0;
        isY = false;
        i++;
    }

    cin >> polecenie;
    cin.ignore();

    sort_with_show(a, rozmiar, polecenie);
    return 0;
}