C# Array: quick Sorting, Binary and linear Searching algorithms


C# Array: this is a very detailed article about Arrays. In this article, we will learn what is an array? How a variable is defined, initialize, and learn the most basic algorithms quicksort, binary, and linear search.

C# Arrays

An array is the combination of several values ​​/ objects of the same type in a parent Data structure. The individual values ​​/ objects are called elements of the array and can be addressed individually via an index.

Definition and Construction of C# Array:

Array types are not introduced by an explicit type definition. Rather, they will also be defined together with their variables.

C# Array Variable definition:

The above definition creates a variable of the type array of int elements. The general syntax of the C# array variable definition is:

type specifies the type of elements managed in the c# array and can be any value or reference type. All c# array variables that hold the same type of element (i.e. the same element type have) belong to the same array type.

NOTE: The size or length of the c# array, i.e. the number of elements that can be stored in it, is none Property of the array type (it is a property of the array object to be created)! This is important for defining array parameters because it means that you can add a parameter to double [] param can assign any double array, regardless of its size, when the method is called.

c++ vs java vs c# array definition:

C++ and Java programmers: In C++ the principle was that the declaration of a type of its use must be analog. In C ++, array variables are therefore declared in such a way that the [] brackets do not adhere to the type specification but are appended to the variable name: int field []. Both spellings were allowed in Java and in C# after all, the brackets are only behind the type!

Array Construction:

The above definition creates an array type and a c# array variable, but not yet a c# array object. Arrays belong to the reference types in C#. Your objects are therefore created with the keyword new. The following statement creates an int array and assigns it to the numbers array variable:

The total number of elements that an array can hold is calculated when the c# array object is created in the square brackets are given and cannot be changed later. If the size of the c# array is fixed at compile-time, this is no problem. Sometimes the number is the elements to be recorded, however, only at runtime and is difficult or possibly impossible to estimate. In these cases, you benefit from the fact that the size specification does not have to be literal, but from can exist in any expression that returns an int value. Under certain circumstances, you can proceed that you let the program calculate the size, save it in a variable and use this then create the c# array:

If the size is not to be determined at compile time or at runtime, you must either move it up an estimate or on a dynamic data container, i.e. one of the predefined listing classes.

Memory usage for c# arrays:

The new array is created as an object in memory. Is it an array of value-type elements? the memory area of ​​the array includes the memory for the individual elements (see figure 1). The individual elements are initialized with the default value of their type.

C# Array
Figure 1

In the case of arrays of reference types, only memory cells for the Element references reserved and initialized to zero. For creating the associated objects and the  programmer is responsible for storing the associated references in the c# array.

C# Array

C# Array Accessing  elements:

To access a specific element in a c# array, append the element’s position as an index in square brackets after the array name. Note, however, that the numbering of the elements in the Array begins with 0, so the first element in the array has index 0. So if you want to assign the value 12 to the first element in the numbers array, write:

If you want to assign twice the value of the first element to the second element, write:

Note: The first element in an array has the index 0! The last index is the number of elements in the array minus

If you use an index for which there is no element, throw an IndexOutOfRangeException.

C# Array Initialization lists:

C# Array objects can also be created implicitly using an initialization list. In this will simply list the values ​​to be included as elements in the c# array. The size of the Array object results automatically from the number of values ​​listed

or shorter:

The compiler implicitly creates a suitable array object and initializes its elements with the values from the initialization list and saves the reference to the object in the array variable.

System.Array in C#:

Certain tasks keep recurring when programming with arrays. Here comes the programmer benefit that all arrays go back to the base class System.Array, which is not just different passes useful properties and methods to the array objects, but also a number of provides interesting static methods for programming with arrays. A selection of these properties and methods are presented below.

Convert c# arrays to strings:

Sometimes it is very useful to output the contents of an array as a string – even if only for the Debug the program. Whoever hopes, however, will only use the one offered by the Array class for this purpose ToString () method will be disappointed: The Array class just takes over the implementation inherited from Object, i.e. the type of the array object is returned. For one The programmer has to create a useful string representation of the array content himself, by converting the individual array elements into strings and outputting them. The following fragment demonstrates how an array is converted into a string array, which can then be used for the Output is processed:

In C# 2.0, as an alternative to converting any array to a string array, you can use the Use Array.ConvertAll() and a converter. The latter is a generic one Delegate, to whom you can specify the source type, the target type and the Transfer method previously defined by you.

 Example: the Conversion of C# arrays to strings:


Determine the c# array length:

The size or length of an array is equal to the number of elements in the array. It doesn’t matter whether or not you have stored your own values ​​in the elements. An array defined as follows:

Therefore has a length of 12. The length of an array can be queried using the Length property:

The Length property is mostly used in connection with looping through arrays.

C# arrays through Loop:

With the help of loops, you can easily loop through arrays of any size, element by element to edit. The loop variable is mostly used as an index for accessing the elements.

If you only have read access to the c# array elements in the loop and no need for the index tag either i, you can alternatively use the foreach syntax:

Delete element from C# array:

You cannot delete the elements of an array in the sense of “removing from the array”. But you can delete the values ​​stored in the elements by setting the elements to their null values (0, false or zero) – either using a loop or by calling the System.Array Method Clear():

As the first argument, you pass Clear() the array variable that refers to the array object to be processed refers. The second argument is the index of the first item to be deleted, the third argument is the Number of items to be deleted.

Copy C# array:

The System.Array class provides three different methods for copying arrays:




Copy whole C# array with Clone()

If you call Clone() on an existing c# array, the method creates a new array object and copies the values ​​from the first array to the corresponding elements of the new array. Finally delivers the method returns a reference to the newly created array object as a result. Need that reference All you have to do is convert it to the correct array type and assign it to a second array variable:

If the c# array to be copied contains elements of reference types, only the references are copied. If So if you copy an array with objects of a self-defined class with Clone (), the elements refer in the new array to the same objects as the elements of the source array.

Insert c# array into other array with CopyTo():

You can insert the elements of an arrayA into an arrayB using the CopyTo() method.

The newly inserted elements replace the old elements in the appropriate positions so that arrayB thereafter contains the following elements:

Insert subarrays into other c# array with Array.Copy():

The static method Copy () works very similarly to CopyTo (), but is a bit more flexible because it allows that Copying a part of an array. First, you pass the source array and the location of the Element to be copied first. Then pass in the target array and the location of the Element to be replaced first. The last argument is the number of items to be copied.

C# Array Sorting:

One of the most powerful sorting algorithms is quicksort. To search for the quicksort in C# arrays To sort methods, all you have to do is call the Sort() method of System.Array:

Calling the above program leads to the following output:

In order for the Sort() method to be able to sort the elements of an array, it must sort the individual elements compare and determine “size differences”. By default, it uses the Interface IComparable, i.e. the Sort() method expects the array elements as objects of the type IComparable can be handled and compared with the IComparable method CompareTo(). IComparable is implemented for numbers and strings, among other things:

  • For numeric types, IComparable is implemented in such a way that the numbers according to their natural Order.
  • IComparable is implemented for strings in such a way that the strings are compared character by character. The decision as to which character of a comparison pair is larger depends on the positions of the characters in the character set, uppercase and lowercase letters and the cultural peculiarities (consideration of the alphabet, umlauts etc.).
  • IComparable can easily be implemented for objects of their own class types.

System.Array methods for sorting in C#:

There are several ways to influence sorting:

For partial C# array:

If you only want to sort a subrange, pass the index of the first element to be sorted and the index that follows the last element to be sorted:



To sort an C# array descending (more precisely, in the opposite direction than specified by the compareTo() method of the elements), simply call the Reverse() method after sorting:

Own Sorting:

Finally, you can make yourself completely free from sorting by IComparable by selecting Sort(). Pass Comparator object (object whose class implements the IComparer interface). Instead of calls the IComparable method compareTo(), passes the element pairs to be compared Sort() then the element pairs to the Compare () method of the comparator:

C# Array QuickSort Algorithm:

One of the most powerful sorting algorithms is C. A. R. Hoare’s Quicksort algorithm, which its name with the development of this algorithm has undoubtedly made it immortal. Using the example at this point, the basic concepts of sorting algorithms are presented. One of the basic requirements for virtually any sort algorithm for data containers is that no sorted copy of the container should be created, but the algorithm can move the container by of the individual elements sorted. The heart of most sorting processes is therefore the exchange two elements in the container:

Which elements should be exchanged in this way?

C# Array

According to the idea of ​​the quicksort algorithm, the middle element of the container is used as a reference value and compares this value with all other elements. Elements that are smaller than the reference value, copied into the half to the left of the reference value and values ​​that are greater than that Reference value, in the half to the right of the reference value. So that this happens as efficiently as possible one tries to swap a value from the left half for a value from the right half (see the above Figure).

Steps of Quicksort Algorithm:

  • So the algorithm goes through the elements of the left half from the outside to the inside until it comes to an Element encounter that is greater than the reference value (in the figure the value 9).
  • Then he goes through the elements of the right half analogously from the outside to the inside until he clicks on Element encounters that is smaller than the reference value (in the figure the value 4).
  • Now both values ​​are exchanged for each other.
  • Steps 1 to 3 are repeated until the cursor for the left and right elements are located.

Then only the two parts to the left and right of the reference element have to be sorted. To do this, you simply call the Quicksort() method recursively.

How to solve C# Array with Quicksort algorithm using the recursive method:


C# Array

Binary search in C# Array:

Sorted c# arrays can be searched very efficiently. The method of choice here is the binary search, BinarySearch() also has a suitable method of the System.Array. You need the method just pass the sorted array and the object to be searched for. The search object is according to the specifications the IComparable method CompareTo() is compared with the elements in the array. Will be a match is found, the method returns the index of the corresponding element, otherwise a negative number.

Example: how to search an element in a C# Array with the help of binary search:


C# Array

C# Array

System.Array BinarySearch() methods:

The BinarySearch() method is overloaded several times. With the help of the overloaded versions, you can subdivide Search through an array or specify yourself how the elements in the c# array are compared.

static int BinarySearch (Array array, Object value):

Checks whether value is present in the passed sorted c# array. Returns the index of the element or a negative number, if no corresponding element available.

The elements are determined according to the specifications of the IComparable Interface compared.

static int BinarySearch (Array array, Object value, IComparer comp):

As above. The elements are passed according to the specifications of the IComparer object compared.

static int BinarySearch (Array array, int index, int length, Object value):

Checks whether value is in the range [index, index + length) of the passed sorted array exists. Returns the index of the Element or a negative number, if no corresponding number Element present.

The elements are determined according to the specifications of the IComparable Interface compared.

static int BinarySearch (Array array, int index, int length, Object value, IComparer comp):

As above. The elements are passed according to the specifications of the IComparer object compared.

C# Array Linear search algorithm:

Example how to sort c# array with the help of linear search algorithm:


C# Array

C# Array

C# Array methods for linear search

Instead of implementing your own loops, you can also use the Find methods of the Access class System.Array.

static bool Exists<T> (T[] array, Predicate<T> match ):

Checks whether array contains elements that meet the condition match suffice.

static T Find<T> (T[] array, Predicate<T> match ):

Returns the first element in c# array that meets the condition match Fulfills. If no element was found, the null value of the type is returned.

static T[] FindAll<T> (T[] array, Predicate<T> match )

Returns an array with all elements from c# array that the Meet the match condition. If no element was found, an empty array is returned.

static T FindIndex<T> (T[] array, Predicate<T> match ):

Returns the index of the first element in c# array that the Condition match met.

static T FindIndex<T> (T[] array, int start, Predicate<T> match ):

If no element was found, -1 is returned.

static T FindIndex<T> (T[] array, int start, int count, Predicate<T> match ):

You can instruct the overloaded versions to start at a certain Position (start) and for a certain number of elements (count) to look for.

static T FindLast<T> (…):

Like Find(), except that the last element is returned.

static T[] FindLastIndex<T> (…):

Like FindIndex(), except that the index of the last element is returned.


Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button